Problem:


Score : 400 points

Problem Statement

You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  

() is a correct bracket sequence.

If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.

If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.

Every correct bracket sequence can be derived from the rules above.

Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

Constraints

The length of S is N.

1 ≤ N ≤ 100

S consists of ( and ).

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

Sample Input 1

3
())

Sample Output 1

(())

Sample Input 2

6
)))())

Sample Output 2

(((()))())

Sample Input 3

8
))))((((

Sample Output 3

(((())))(((())))



Sample input:
3
())


Sample output:
(())

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n = II()
    s = IS()
    dq = deque()
    l_cnt = r_cnt = 0
    for si in s:
        # print(''.join(dq))
        if si == '(':
            l_cnt += 1
            dq.append(si)
        elif si == ')':
            if l_cnt == 0:
                dq.appendleft('(')
                dq.append(si)
            elif l_cnt > 0:
                dq.append(si)
                l_cnt -= 1
    for _ in range(l_cnt):
        dq.append(')')

    print(''.join(dq))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N = int(input())
    S = str(input())
    stack_rem = 0

    need_left = 0

    for i in range(N):
        if S[i] == '(':
            stack_rem += 1
        elif stack_rem > 0:
            stack_rem -= 1
        else:
            need_left += 1
    need_right = stack_rem
    print('('*need_left+S+')'*need_right)

resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N = int(input())
    S = str(input())
    pointer = 0
    need_left = 0

    for i in range(N):
        if S[i] == '(':
            pointer += 1
        else:
            if pointer == 0:
                need_left += 1
            else:
                pointer -= 1

    need_right = pointer
    print('('*need_left+S+')'*need_right)

resolve()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = input().rstrip('\n')

    balance = 0
    balance_min = 0
    for s in S:
        if s == "(":
            balance += 1
        else:
            balance -= 1
        balance_min = min(balance_min, balance)
    ans = S
    if balance_min < 0:
        ans = "(" * (balance_min * -1) + S
        balance -= balance_min
    if balance > 0:
        ans += ")" * balance
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N = int(input())
    S = str(input())
    left_over = 0
    right_over = 0

    for i in range(N):
        if S[i] == '(':
            left_over += 1
        else:
            left_over -= 1
            if left_over < 0:
                right_over = max(right_over, -left_over)

    SS = '('*right_over+S

    left_over = 0
    for i in range(len(SS)):
        if SS[i] == '(':
            left_over += 1
        else:
            left_over -= 1

    print(SS+')'*left_over)


resolve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()

stock_left = 0
num_new_l = 0
for i in range(n):
    if s[i] == '(':
        stock_left += 1
    else:
        if stock_left > 0:
            stock_left -= 1
        else:
            num_new_l += 1

stock_right = 0
num_new_r = 0
for i in range(-1,-n-1,-1):
    if s[i] == ')':
        stock_right += 1
    else:
        if stock_right > 0:
            stock_right -= 1
        else:
            num_new_r += 1

new_l = '(' * num_new_l
new_r = ')' * num_new_r
print(new_l + s + new_r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def f(S):
    '''
    >>> f('(')
    '('
    >>> f(')(')
    ')('
    >>> f('()')
    ''
    >>> f('(())(')
    '('
    >>> f('())')
    ')'
     '''
    stack = []
    for s in S:
        if s == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(')')
        else:
            stack.append(s)
    return ''.join(stack)


def solve(N: int, S: str):
    s = f(S)
    return '(' * s.count(')') + S + ')' * s.count('(')


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    print(solve(N, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input())
S = input()

left = [] 

for i, s in enumerate(S):
    if s == "(":
        left.append("(")
    else:
        if len(left) > 0:
            left.pop()
        else:
            S = "(" + S

for _ in range(len(left)):
    S += ")"

print(S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

sl = 0
sr = 0
slmax = 0
srmax = 0
for i in range(N):
  if(S[i] == '('):
    sl -= 1
  else:
    sl += 1
  slmax = max(slmax, sl)
for i in range(N):
  if(S[N-i-1] == '('):
    sr += 1
  else:
    sr -= 1
  srmax = max(srmax, sr)
for i in range(slmax):
  S = '(' + S
for i in range(srmax):
  S = S + ')'
print(S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
LR = [0,0]
l = "("
r = ")"

for i in range(N):
  if S[i] == r:
    if LR[1] == 0:
      LR[0] += 1
    else:
      LR[1] -= 1
  elif S[i] == l:
    LR[1] += 1

S = l * LR[0] + S + r * LR[1]

print(S)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

n = int(input())
s = input()

op, cl = 0 ,0
# sを右から調べていく
# s[i]が何なら何が必要になるのか
for c in s:
    if c == '(':
        op += 1
    else:
        if op > 0:
            op -= 1
        else:
            cl += 1
# 追加するのは左に'('いくつか右に')'いくつか
print(('(' * cl) + s + (')' * op))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

c = [0,0]
for s in S:
    if s == '(':
        c[0] += 1
    else:
        if c[0] > 0:
            c[0] -= 1
        else:
            c[1] += 1

pre = ['('] * c[1]
rear = [')'] * c[0]
ans = pre+S+rear
print(''.join(ans))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
d=[0]*n
lcount=0
rcount=0
for i in range(len(s)):
  if s[i]=="(":
    lcount+=1
  else:
    if lcount>=1:
      lcount-=1
    else:
      rcount+=1

print("("*rcount+s+")"*lcount)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
s=input()
ans=deque(s)
cnt=0
for i in range(n):
  if (cnt==0)and(s[i]==')'):
    ans.appendleft('(')
  elif (cnt!=0)and(s[i]==')'):
    cnt-=1
    pass
  elif s[i]=='(':
    cnt+=1
if cnt>0:
  ans.append(')'*cnt)
print(''.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
SL = [0]
for i in range(N):
    if S[i] == '(':
        SL.append(SL[i] + 1)
    else:
        SL.append(SL[i] - 1)

mi = min(SL)
la = SL[-1]
if mi < 0:
    S = '(' * ((-1)*mi) + S
    la -= mi
if la >= 0:
    S += ')' * la
else:
    p = (-1)*la
    S = '(' * p + S

print(S)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

left=0
cnt1=0
cnt2=0

for i in range(N):
    if S[i]=="(":
        cnt1+=1
    elif S[i]==")":
        cnt2+=1
        if i<N-2 and S[i+1]=="(":
            if cnt2>=cnt1+left:
                left=cnt2-cnt1

res=S.count("(")+left-S.count(")")
if res>=0:
    print("("*left+S+")"*res)
else:
    print("("*(left+abs(res))+S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

L = 0
R = 0
cnt = 0
d = []
for s in S:
    if s == "(":
       cnt += 1
    else:
        cnt -= 1
        if cnt < 0:
            cnt = 0
            L += 1

R += cnt

print(L*"(" + S + R*")")

Submission status: Accepted

Solution code:

def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

N = int(input())
S = input()

l, r = hoge(S)
print('(' * l + S + ')' * r)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cnt=0
ans=str()
for i in range(n):
    if s[i]=="(":
        cnt+=1
        ans+="("
    elif s[i]==")":
        if cnt>0:
            cnt-=1
            ans+=")"
        else:
            ans=ans[::-1]
            ans+="("
            ans=ans[::-1]
            ans+=")"
            cnt=0

if cnt>0:
    while cnt>0:
        ans+=")"
        cnt-=1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
stack= []
ans=""
L=0
R=0

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      stack.pop()
    else:
      L += 1

R=len(stack)
ans = L * "(" + S + R * ")"

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    S = input()
    l,r = 0,0
    state = 'r'
    for i in range(N):
        if i == 0 and S[i] == ')': state = 'l'
        # if S[i] == '(': state = 'r'
        if i > 0  and S[i-1] == ')' and S[i] == '(':
            state = 'r' 
            
        if S[i] == '(':
            if state == 'l':
                if l > 0:
                    l -= 1
                else:
                    r += 1
            elif state == 'r':
                r += 1
        elif S[i] == ')':
            if state == 'r':
                if r > 0:
                    r -= 1
                else:
                    l += 1
            elif state == 'l':
                l += 1
                
        # print(state,l,r)
            
    print('('*l+S+')'*r)
    
solve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
st=0
m=0
lv = 0
for x in s:
    if x == '(':
        lv+=1
    else:
        lv-=1
    m=min(m,lv)
gl=lv-m
st-=m
print('('*st+s+')'*gl)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
total,min_total = 0, 1
for s in S:
    total += 1 if s == '(' else -1
    if total < min_total:
        min_total = total    
print('('*-min_total+S+')'*(total-min_total) if min_total<0 else S+')'*total)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dist = 0
mlow = 0
for i in s:
    if i == ")":
        dist -= 1
        if dist < mlow:
            mlow = dist
    else:
        dist += 1

left = "("*(-mlow)
right = ")"*(dist-mlow)
print(left+s+right)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    pls_left = 0
    pls_right = 0
    for s in S:
        if s == '(':
            pls_right += 1
        else:
            if pls_right == 0:
                pls_left += 1
            else:
                pls_right -= 1

    res = '(' * pls_left + S + ')' * pls_right

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    pls_left = 0
    pointer = 0
    for s in S:
        if s == '(':
            pointer += 1
        else:
            if pointer == 0:
                pls_left += 1
            else:
                pointer -= 1

    pls_right = pointer
    res = '(' * pls_left + S
    res += ')' * pls_right

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()

result=""
cnt=0

#(を追加する
for ss in s:
    #print(result)
    if ss ==")":
        if cnt>0:
            result+=ss
            cnt-=1
        else:
            result="("+result+ss

    else:
        result+=ss
        cnt+=1

L=result.count("(")
R=result.count(")")

result+=")"*(L-R)

print(result)

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
l, r = 0, 0
for s in S:
    if s == "(":
        l += 1
    else:
        r += 1
        if l > 0:
            l -= 1
            r -= 1
print("("*r+S+")"*l)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = 0
cnt = 0
for c in S:
    if c == "(":
        cnt += 1
    else:
        if cnt == 0:
            l += 1
        else:
            cnt -= 1
ans = "("*l + S + ")"*cnt
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = max(0,-min(SSS))
M = SSS[-1]
print('('*m+S+')'*(M+m))

Submission status: Accepted

Solution code:
n=int(input())
s=str(input())

ans=0#(
count1=0
for i in range(n):
    if s[i]=='(':
        count1+=1
    else:
        if count1==0:
            ans+=1
        else:
            count1-=1

for i in range(ans):
    print('(',end="")
print(s,end="")
for i in range(count1):
    print(')',end="")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    left = 0
    right = 0
    for i in range(n):
        if s[i] == '(':
            right += 1
        else:
            if right == 0:
                left += 1
            else:
                right -= 1
    print('('*left+s+')'*right)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())

s = input()

now =0
right = 0
for i in range(n):
    if(s[n-1-i]=='('):
        now+=1
    else:
        now-=1
    if(right<now):
        right=now
left=0
now=0
for i in range(n):
    if(s[i]=='('):
        now-=1
    else:
        now+=1
    if(left<now):
        left=now

print('('*left +s+ ')'*right)

Submission status: Accepted

Solution code:
n = int(input())
x = list(input())
sta = 0
left = 0
for i in range(n):
    if x[i] == '(':
        sta += 1
    else:
        if sta == 0:
            left += 1
        else:
            sta -= 1
s = []
for i in range(left):
    s.append('(')
for i in range(n):
    s.append(x[i])
for i in range(sta):
    s.append(')')
print(''.join(s))

Submission status: Accepted

Solution code:
n = int(input())
t = input()
lef = 0
rig = 0
cl = 0
cr = 0

for i in range(n):
    if t[i] == ")":
        rig += 1
        if rig > lef+cl:
            cl += 1
    if t[i] == "(":
        lef += 1
lef = 0
rig = 0
for i in reversed(range(n)):
    if t[i] == "(":
        lef += 1
        if lef > rig+cr:
            cr += 1
    if t[i] == ")":
        rig += 1

for i in range(cl):
    print("(",end="")
print(t,end="")
for i in range(cr):
    print(")",end="")

Submission status: Accepted

Solution code:
input()
s = input()
d = 0
x = 0
for c in s:
    if c == "(":
        d += 1
    else:
        d -= 1
    x = min(d, x)
print("(" * -x + s + ")" * (d - x))

Submission status: Accepted

Solution code:
# 2020/05/06
# AtCoder Beginner Contest 064 - D

# Input
n = int(input())
s = list(input())
nestlv = 0
nestmax = 0
nestmin = 0
lcnt = 0
rcnt = 0

for i in range(n):
    if s[i] == '(':
        nestlv = nestlv + 1
        nestmax = max(nestmax, nestlv)
    elif s[i] == ')':
        nestlv = nestlv - 1
        nestmin = min(nestmin, nestlv)

ans = ''.join(s)
for i in range(nestmin*(-1)):
    ans = '(' + ans

nestlv = nestlv - nestmin
if nestlv > 0:
    for i in range(nestlv):
        ans = ans + ')'

# Output
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

cs=0
mincs=1000
enc={'(':1,')':-1}

for c in S:
    cs+=enc[c]
    mincs=min(mincs,cs)

while mincs<0:
    S='('+S
    mincs+=1
    cs+=1

while cs>0:
    S=S+')'
    cs-=1

print(S)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
s = input()
cnt = 0
left = 0
for i in range(n):
    if s[i] == "(":
        cnt += 1
    elif cnt > 0:
        cnt -= 1
    else:
        left += 1
ans = "(" * left + s + ")" * cnt
print(ans)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  s=input()
  sl,sr=[0],[0]# sl:(,  sr:)
  l,r=0,0
  for si in s:
    if si=='(':
      l+=1
    else:
      r+=1
    sr.append(r)
    sl.append(l)
  ans=n
  al,ar=0,0
  for i in range(n):
    if s[i]=='(':
      a=(sl[n]-sl[i+1])-(ar+sr[n]-sr[i+1])
      if a>=0:
        ar+=a+1
    else:
      a=sr[i]-(al+sl[i+1])
      if a>=0:
        al+=a+1
  print('('*al+s+')'*ar)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
#print(S)

S_orig=list(S)
while True:
  update=False
  
  remove_flg=[False]*len(S)
  for i in range(1,len(S)):
    if S[i-1]=='(' and S[i]==')':
      remove_flg[i-1]=remove_flg[i]=True
      update=True      
  if not update:
    break
      
  new_S=[]
  for i in range(len(S)):
    if not remove_flg[i]:
      new_S.append(S[i])      
  S=new_S
  
cnt_l=cnt_r=0
for i in range(len(S)):
  if S[i]=='(':
    break
  else:
    cnt_l+=1
for i in reversed(range(len(S))):
  if S[i]==')':
    break
  else:
    cnt_r+=1
#print(cnt_l,cnt_r)

answer_S=['(']*cnt_l+S_orig+[')']*cnt_r
print("".join(answer_S))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

front_not_close = 0
end_not_close = 0

for s in list(S):
    if s == '(':
        front_not_close += 1
    else:
        if front_not_close > 0:
            front_not_close -= 1
        else:
            end_not_close += 1


for i in range(end_not_close):
    S = '(' + S

for i in range(front_not_close):
    S = S + ')'

print(S)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()
    stack = deque([])
    left = 0
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if len(stack) == 0:
                left += 1
            else:
                _ = stack.pop()

    right = len(stack)
    ans = "(" * left + S + ")" * right
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()

d = [0] * (N + 1)
for i in range(N):
    d[i + 1] = d[i] + int(S[i] == "(") - int(S[i] == ")")

a = d[-1]
b = min(d)

print("(" * -b + S + ")" * (a - b))

Submission status: Accepted

Solution code:
n = int(input())
s = input()

r = 0
l = 0
for i in s:
    if i == "(":
        r += 1
    else:
        if r == 0:
            l += 1
        else:
            r -= 1

else:
    print("("*l + s + ")"*r)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ss = s
l = 0
for c in ss:
    if c == "(":
        l += 1
    else:
        if l > 0:
            l -= 1
        else:
            s = "(" + s
for i in range(l):
    s = s + ")"
print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l=0
r=0
for i in s:
    if i ==')' and l==0:
        r+=1
    elif i==')':
        l-=1
    elif i=='(':
        l+=1
s1 = '('*r
s2 = ')'*l
s=s1+s+s2
print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
ans = "".join(s)

f = True
while f:
    f = False
    l = [True] * len(s)
    ns = []
    for i in range(len(s)-1):
        if (s[i] == "(") and (s[i + 1] == ")"):
            l[i], l[i + 1] = False, False
            f = True

    for i in range(len(s)):
        if l[i]:
            ns.append(s[i])

    s = ns.copy()

cnt = [0, 0]
for c in s:
    cnt[c == "("] += 1

print("(" * cnt[0] + ans + ")" * cnt[1])

Submission status: Accepted

Solution code:
n = input()
s = input()
count = 0
max_l = 0
max_r = 0

for c in s:
    if c =="(":
        count -= 1
    else:
        count += 1
    max_l = max(max_l, count)
count = 0
for c in s[::-1]:
    if c =="(":
        count += 1
    else:
        count -= 1
    max_r = max(max_r, count)

print("("*max_l + s + ")"*max_r)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

right = 0
left = 0

for i in range(n):
    temp = s[i]
    if temp == '(':right += 1
    else:
        if right == 0:
            left += 1
        else:
            right -= 1

ans = left * '(' + s + right * ')'
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
a=0
b=0
c=0
for i in range(n):
    d=s[i]
    if d=='(':
        a+=1
    else:
        b+=1
        if b-c>a:
            c+=1
print('('*c+''.join(s)+')'*(a-b+c))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
from collections import deque
q = deque([])

if S == '(' or S == ')':
    print('()')
    exit()

l = []
cnt = 0
for i in range(N-1):
    if S[i] == '(':
        cnt += 1
        if S[i+1] == ')':
            l.append(['a', cnt])
            cnt = 0
        elif S[i+1] == '(' and i+1 == N-1:
            l.append(['a', cnt+1])
            cnt = 0
    elif S[i] == ')':
        cnt += 1
        if S[i+1] == '(':
            l.append(['b', cnt])
            cnt = 0
        elif S[i+1] == ')' and i+1 == N-1:
            l.append(['b', cnt+1])
            cnt = 0

if S[-1] != S[-2]:
    if S[-1] == '(':
        if l[-1][0] == 'a':
            l[-1][1] += 1
        else:
            l.append(['a', 1])
    elif S[-1] == ')':
        if l[-1][0] == 'b':
            l[-1][1] += 1
        else:
            l.append(['b', 1])


a = 0
b = 0
for i in range(len(l)):
    k, c = l[i]
    if k == 'a':
        q.append('('*c)
        a += c
    if k == 'b':
        q.append(')'*c)
        b += c
        if a < b:
            q.appendleft('('*(b-a))
            a += (b-a)
if a > b:
    q.append(')'*(a-b))

print(*q, sep='')

Submission status: Accepted

Solution code:
def abc064_d():
  _ = int(input())
  s = str(input())
  # 後ろから見ていく
  srev = s[::-1]
  # 開きカッコ閉じカッコの個数(追加分を含む)
  op, cl = 0, 0
  # 追加したものを入れる
  f, r = '', ''
  for c in srev:
    if c == '(': op += 1
    else: cl += 1
    # 開きカッコが先行したら、都度、閉じカッコを末尾に追加
    if op > cl:
      r += ')'
      cl += 1
  else:
    # 先頭に開きカッコを足す
    f += '(' * (cl - op)
  # 元の文字列sにfとrを足す
  ans = f + s + r
  print(ans)

abc064_d()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cntl=0
for i in range(n-1,-1,-1):
    if s[i]==")":
        cntl+=1
    elif s[i]=="(" and cntl>0:
        cntl-=1
sl="("*cntl
cntr=0
for i in range(n):
    if s[i]=="(":
        cntr+=1
    elif s[i]==")" and cntr>0:
        cntr-=1
sr=")"*cntr
print(sl+s+sr)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=s
while len(s)>0:
  s=ans
  i=0
  while i<len(s):
    if s[i:i+2]=='()':
      s=(s[:i]+s[i+2:] if i!=0 else s[i+2:])
      i=-1
    i+=1
  l=s.count('(')
  r=s.count(')')
  if l>r :
    ans=ans+')'*(l-r)
  elif r>l:
    ans='('*(r-l)+ans
  elif len(s)>0:
    ans='('+ans
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=input()
def check_l(A):
    for i in range(1,len(A)+1):
        if not i==len(A):
            if A[-i]=="(":
                pass
            else:
                return i
                break
        elif i==len(A):
            if A[-i]=="(":
                return 0
            else:
                return i
                break
def check_t(A):
    for i in range(0,len(A)):
        if not i==len(A)-1:
            if A[i]==")":
                pass
            else:
                return i
                break
        elif i==len(A)-1:
            if A[i]==")":
                a=len(A)
                return a
            else:
                return i
def all(A,C):
    if check_l(A)==0:
        for i in range(len(A)):
            C=C+")"
        print(C)
        exit()
    elif not check_l(A)==0:
        for i in range(check_l(A)-1):
            A=A+")"
            C=C+")"

    if check_t==len(A):
        for i in range(len(A)):
            C="("+C
        print(C)
        exit()
    else:
        for i in range(check_t(A)):
            A="("+A
            C="("+C

    for i in range(10**9):
        if "()" in A:
            A=A.replace("()","")
        else:
            break
    return A,C

X=A

for i in range(N):
    if A=="":
        print(X)
        break
    else:
        A,X=all(A,X)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
over=0
left=0
right=0
center=""
for i in s:
    if over==0 and i==")":
        left+=1
    elif over!=0 and i==")":
        over-=1
    else:
        over+=1
    center+=i
right=over
print("("*left+center+")"*right)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    S = input()

    insert_L = 0
    cnt_L = 0

    for s in S:
        if s == '(':
            cnt_L += 1
        else:
            if cnt_L:
                cnt_L -= 1
            else:
                insert_L += 1

    insert_R = cnt_L

    res = '(' * insert_L + S + ')' * insert_R
    print(res)


if __name__ == '__main__':
    resolve()