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:
N = int(input())
S = input()
left = 0
right = 0
k = 0
for c in S:
    if c == "(":
        left += 1
    else:
        right += 1
        if left < right:
            left = right
            k += 1
ans = ""
for i in range(k):
    ans += "("
ans += S
for i in range(left-right):
    ans+=")"
print(ans)

Submission status: Accepted

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

before = 0
after = 0
for i in s:
    if i == '(':
        after += 1
    elif i == ')':
        if after > 0:
            after -= 1
        else:
            before += 1

print('('*before + s + ')'*after)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
m = [0,0]

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

for i in range(m[0]):
    S += ')'
for i in range(m[1]):
    S = '(' + S

print(S)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7


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


l,r = 0,0
stack = 0
for i in range(N):
    if S[i]==")":
        if stack > 0:
            stack -= 1
            r -= 1
        else:
            l += 1
    else:
        r += 1
        stack += 1

print("("*l+S+")"*r)

Submission status: Accepted

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

Submission status: Accepted

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

l = 0
p = 0
for i in range(n):
    if s[i]=='(':
        l+=1
    elif l>0:
        p+=1
        l-=1

a = s.count('(')
b = s.count(')')

print('('*(b-p)+s+')'*(a-p))

Submission status: Accepted

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

def solve(s):
  add_left = 0
  add_right = 0
  for c in s:
    if c == '(':
      add_right += 1
    elif add_right == 0:
      add_left += 1
    else:
      add_right -= 1
  return '(' * add_left + s + ')' * add_right

ans = solve(S)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = 0 # (
r = 0 # )
for c in S:
  if c == '(': l += 1
  else:
    if l == 0: r += 1
    else: l -= 1
print('(' * r + S + ')' * l)

Submission status: Accepted

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


def solve(N: int, S: str):
    left = 0
    left_max = 0
    for i in range(N):
        if S[i] == ')':
            left += 1
        elif S[i] == '(':
            left -= 1
        if left > left_max:
            left_max = left
    
    right = 0
    right_max = 0
    for i in range(N-1, -1, -1):
        if S[i] == '(':
            right += 1
        elif S[i] == ')':
            right -= 1
        if right > right_max:
            right_max = right
    print('(' * left_max + S + ')' * right_max)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    s= input().strip()


    diff = 0
    cnt_inbal = 0
    cnt_l = 0
    for i in range(n):
        if s[i]=='(':
            diff += 1
            cnt_l += 1
        else:
            diff -= 1
            if diff < 0:
                cnt_inbal += 1
                diff = 0

    for i in range(cnt_inbal):
        s = '(' + s


    for i in range(cnt_l + cnt_inbal - (n - cnt_l)):
        s += ')'

    print(s)
        
        


solve()

Submission status: Accepted

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

right = 0
left = 0
for i in S:
    if i == '(':
        left += 1
    else:
        if left > 0:
            left -= 1
        else:
            right += 1

ans = ''
for i in range(right):
    ans += '('
ans += S
for i in range(left):
    ans += ')'

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
r = 0
lr = 0
li = 0
for i in range(n):
    if s[i] == '(':
        li = i
        break
    if i==n-1:
        li = i
for i in range(li, n):
    if s[i] == '(':
        lr += 1
    else:
        if lr > 0:
            lr -= 1
        else:
            r += 1

res = '('*r
res += '('*li
res = res + s + ')' * max(0, lr)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
ans = s

def solve(n,s):
    cnt0 = [0]*n
    cnt1 = [0]*n
    cnt0[0] = 1 if s[0] == '(' else 0
    cnt1[-1] = 1 if cnt1[-1] == ')' else 0
    for i in range(1,n):
        cnt0[i] = cnt0[i - 1]
        if s[i] == '(' :
            cnt0[i] += 1
        elif cnt0[i] > 0:
            cnt0[i] -= 1
    return cnt0[-1]
        

right = solve(N,s)
r_s =''
for i in s:
    if i =='(':
        r_s = ')' + r_s
    else:
        r_s = '(' + r_s
left = solve(N,r_s)
print('('*left + ans + ')'*right)

Submission status: Accepted

Solution code:
#D問題
N=int(input())
S=str(input())
Slist=list(S)
Left=[] #"("
Right=[] #")"
for i in range(N):
    if Slist[i] == "(":
        Left.append(i)
    else:
        if len(Left) == 0:
            Right.append(i)
        else:
            del Left[0]
Llen=len(Left)
Rlen=len(Right)
for i in range(Llen):
    Slist.insert(2*N,")")    
for i in range(Rlen):
    Slist.insert(0,"(")
ans="".join(Slist)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
res = ""
stack = []
for c in s:
    if c=='(':
        res+=c
        stack.append(c)
    else:
        if stack==[]:
            res = '('+res+c
        else:
            stack.pop()
            res+=c
for c in stack:
    res+=')'
print(res)

Submission status: Accepted

Solution code:
n=input()
s=input()
x=s
while "()" in x:x=x.replace("()","")
print("("*x.count(")")+s+")"*x.count("("))

Submission status: Accepted

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

l = list(s)

value = 0
app_s = 0

for j in range(0,n):
    i = l[j]
    if i == "(":
        value = value + 1
    else:
        value = value - 1
        if -app_s > value:
            app_s = -value

if app_s > 0:
    for j in range(0,app_s):
        s = "(" + s

value = value + app_s

if value > 0:
    for j in range(0,value):
        s = s + ")"

print(s)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l,r=0,0
for i in s:
    if i=="(":
        r+=1
    else:
        if r<=0:
            l+=1
        else:
            r-=1
print("("*l+s+")"*r)

Submission status: Accepted

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

def check_rank(s):
    count = 0
    rank = [0] * len(s)
    for i, c in enumerate(s):
        if c == ")":
            count -= 1
        if c == "(":
            count += 1
        rank[i] = count
    return rank

r = check_rank(s)

if min(r) < 0:
    s = abs(min(r)) * "(" + s
    r = check_rank(s)

if r[-1] > 0:
    s = s + ")" * r[-1]
    r = check_rank(s)

print(s)

Submission status: Accepted

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

l_cnt = 0
for s in S[::-1]:
    if s == ')':
        l_cnt += 1
    elif s == '(':
        if l_cnt != 0:
            l_cnt -= 1

r_cnt = 0
for s in S:
    if s == '(':
        r_cnt += 1
    elif s == ')':
        if r_cnt != 0:
            r_cnt -= 1
            
print('(' * l_cnt + S + ')' * r_cnt)

Submission status: Accepted

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

need_left = 0
cnt = 0
for i in range(N):
    if s[i] == "(":
        cnt += 1
    else:
        if cnt == 0:
            need_left += 1
        else:
            cnt -=1
need_right = cnt
ans =""
for i in range(need_left):
    ans +="("
ans += s
for i in range(need_right):
    ans += ")"
print(ans)

Submission status: Accepted

Solution code:
n = input()
s = input()
ltmp = 0
ladd = 0
for c in s:
    if c == ")":
        if ltmp == 0:
            ladd += 1
        else:
            ltmp -= 1
    else:
        ltmp += 1
        
print("(" * ladd + s + ")" * ltmp)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = ns()

stack = []

left = 0
right = 0

for si in s:
    if si == '(':
        stack.append('(')
        
    elif si == ')':
        if stack:
            stack.pop()
        else:
            left += 1
            
right = len(stack)

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

Submission status: Accepted

Solution code:
N = int(input())

S = input()
while True:
	nl = 0
	nr = 0
	j = "O"
	for i in S:
		if i == "(":
			nl += 1
		else:
			nr += 1
		if nr > nl:
			S = "(" + S
			j = "N"
			break
	if j == "O":
		break

n = S.count("(") - S.count(")")
print(S + n * ")")

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    
    L = ''
    R = ''
    c = 0
    for s in S:
        if s == '(':
            c += 1
        else:
            c -= 1

        if c < 0:
            L += '('
            c += 1

    R += ')' * c

    return L + S + R


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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
t=s
while "()" in s:
    s=s.replace("()","")

print(s.count(")")*"("+t+")"*s.count("("))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
c = [0]
for i in range(n):
    if s[i] == '(':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1] - 1)
print(max(0, -min(c)) * '(' + s + max(0, c[-1] - min(c)) * ')')

Submission status: Accepted

Solution code:
n = int(input())
s = input()
lv = [0] * n

lvi = 0
for i,v in enumerate(s):
    if v == '(' :
        lvi += 1
    else:
        lvi -= 1
    lv[i] = lvi
l = min(0,min(lv))
r = -lv[-1] + l

print('('*(-l) + s + ')'*(-r))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
a = 0
b = 0
sub = 0
for i in range(N):
  if S[i] == '(':
    a += 1
  else:
    b += 1
  if a-b <= sub:
    sub = a-b
S = '('*max((-sub),0)+S+')'*max(a-b-sub,0)
print(S)

Submission status: Accepted

Solution code:
def insertion(N: int, S: str)->str:
    bra, ket = 0, 0
    for c in S:
        if c == '(':
            bra += 1
        else:  # c == ')'
            if bra > 0:  # ペアが作れる
                bra -= 1
            else:  # ペアが作れない。
                ket += 1

    ret = ('(' * ket) + S

    bra, ket = 0, 0
    for c in reversed(S):
        if c == ')':
            ket += 1
        else:  # c == '('
            if ket > 0:  # ペアが作れる
                ket -= 1
            else:  # ペアが作れない
                bra += 1

    ret = ret + (')' * bra)

    return ret


if __name__ == "__main__":
    N = int(input())
    S = input()
    ans = insertion(N, S)
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
d=[0,0]
for i in s:
    if i=="(": d[0]+=1
    if i==")" and d[0]>0: d[0]-=1
for i in s[::-1]:
    if i==")": d[1]+=1
    if i=="(" and d[1]>0: d[1]-=1
s="("*d[1]+s+")"*d[0]
print(s)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = input()
dq = deque()
ans = deque(list(S))
for s in S:
    if not dq:
        dq.append(s)
    else:
        if dq[-1] == "(" and s == ")":
            dq.pop()
        else:
            dq.append(s)
while dq:
    value = dq.popleft()
    if value == ")":
        ans.appendleft("(")
    elif value == "(":
        ans.append(")")
ans = "".join(ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
left = 0
right = 0
i = 0
while i < len(s):
    if s[i] == "(":
        left += 1
    else:
        right += 1
    if left < right:
        s.insert(0,"(")
        left += 1
        i += 1
    i += 1
for i in range(left-right):
    s.append(")")
for i in range(len(s)):
    if i != len(s)-1:
        print(s[i],end="")
    else:
        print(s[i])

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = []
for c in S:
  if c == "(":
    r.append(1)
  else:
    r.append(-1)
ruiseki = [0]
for er in r:
  ruiseki.append( ruiseki[-1] + er )

age = 0
if min(ruiseki) < 0:
  age = abs(min(ruiseki))
  S = "("*abs(min(ruiseki)) + S
if ruiseki[-1] + age > 0:
  S = S + ")"*(ruiseki[-1] + age)
print(S)

Submission status: Accepted

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

i = 0
c = 0
min_c = 0
while i < N:
    if S[i] == "(":
        c += 1
    else:
        c -= 1
    min_c = min(c, min_c)
    i += 1

print("(" * (-min_c) + S + ")" * (c-min_c))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
unclosedBra = 0 #( num
unclosedKet = 0 #) num
for i in range(N):
  if S[i] == '(':
    unclosedBra += 1
  else:
    if unclosedBra > 0:
      unclosedBra -= 1
    else:
      unclosedKet += 1
ans = ('(' * unclosedKet ) + S + (')' * unclosedBra)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
res=S
while '()' in res:
    res=res.replace('()','')
ans='('*res.count(')')+S+')'*res.count('(')
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
que = []
for i in range(n):
  if s[i] == ")" and que and que[-1] == "(":
    que.pop()
  else:
    que.append(s[i])
ket = que.count(")")
bra = len(que) - ket
print("("*ket + s + ")"*bra)

Submission status: Accepted

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

print("("*count2 + s + ")"*count1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    pre = 0
    post = 0
    for i in range(N):
        if S[i] == '(':
            post += 1
        else:
            if post >= 1:
                post -= 1
            else:
                pre += 1
    print('(' * pre + S + ')' * post)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

l, r = 0, 0
for s in S:
    if s == "(":
        l += 1
    elif l:
        l -= 1
    else:
        r += 1

print("(" * r + S + ")" * l)

Submission status: Accepted

Solution code:
N = input()
S = input()
st1 = []
st2 = []
tmp = ''
for x in S:
    if x == '(':
        st1.append(S)
    elif x == ')':
        if len(st1) > 0:
            st1.pop()
        else:
            tmp = '(' + tmp
    tmp += x
ans = tmp
for x in tmp[::-1]:
    if x == ')':
        st2.append(S)
    elif x == '(':
        if len(st2) > 0:
            st2.pop()
        else:
            ans += ')'
print(ans)

Submission status: Accepted

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

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

for j in range(cnt):
    res += ')'
print(res)

Submission status: Accepted

Solution code:
"""
"""

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

# 左から操走
tmp, cnt = 0, 0

for i in s:
    if i == "(":
        tmp -= 1
    else:
        tmp += 1
    cnt = max(cnt, tmp)

ans = "(" * cnt + s

# 右から操走
tmp, cnt = 0, 0
for i in s[::-1]:
    if i == "(":
        tmp += 1
    else:
        tmp -= 1
    cnt = max(cnt, tmp)

ans += ")" * cnt
print (ans)

Submission status: Accepted

Solution code:
#coding:utf-8
N=input()
S=raw_input()

st=[]
for s in S:
    if len(st) >= 1:
        a=st.pop()
        if a == '(' and s == ')':
            continue
        st.append(a)
    st.append(s)
migi=0
hidari=0
for s in st:
    if s == ")":migi+=1
    else: hidari+=1
print "("*migi + S + ")"*hidari

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
f = [0]
for i in range(1,400):
    f.append(0)
for i in range(400,800):
    f.append(1)
for i in range(800,1200):
    f.append(2)
for i in range(1200,1600):
    f.append(3)
for i in range(1600,2000):
    f.append(4)
for i in range(2000,2400):
    f.append(5)
for i in range(2400,2800):
    f.append(6)
for i in range(2800,3200):
    f.append(7)
for i in range(3200,4801):
    f.append(-1)
n = I()
a = LI()
k = [1 for i in range(8)]
s = 0
t = 0
for i in a:
    if f[i] >= 0:
        if k[f[i]]:
            k[f[i]] = 0
            s += 1
    else:
        t += 1
print(max(s,1),min(s+t,n))
"""

#D
n = I()
s = S()
ans = []
k = 0
for i in range(n):
    if s[i] == ")":
        k += 1
    else:
        if k > 0:
            ans += ["("]*k
            k = 0
        k -= 1
if k < 0:
    ans += [")"]*(-k)
else:
    ans = ["("]*k+ans
i = 0
if len(ans) == 0:
    for i in s:
        print(i,end = "")
else:
    while ans[i] == "(":
        i += 1
        if i == len(ans):break
    for j in range(n):
        ans.insert(i+j,s[j])
    for i in ans:
        print(i,end = "")
print()
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

d = [0]
for _s in s:
  if _s == '(':
    d.append(d[-1] + 1)
  else:
    d.append(d[-1] - 1)
x = min(d[1:])
ds = d[-1]

if x > 0:
  print('(' * (-x) + s + ')' * (ds))
else:
  print('(' * (-x) + s + ')' * (ds - x))

Submission status: Accepted

Solution code:
input()
s=input()
while 1:
  for i in range(len(s)):
    if s[i]=='('and s[i:].count(')')<(len(s)-i)/2:
      s+=')'
      break
  else:
    break
print('('*(s.count(')')-s.count('('))+s)

Submission status: Accepted

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

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

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

p = s.count('(')
q = n - p

if left + p < right + q:
    left += (right + q) - (left + p)
elif left + p > right + q:
    right += (left + p) - (right + q)

s = ['('] * left + s + [')'] * right

print(''.join(s))

Submission status: Accepted

Solution code:
def d_insertion(N, S):
    need_left, need_right = 0, 0  # Sの左右にほしい'(', ')'の個数
    for c in S:
        if c == '(':
            # '('と対応する')'を仮に右端に補充することにする。
            # あとで')'が出てきたなら補充量を減らせばいい。
            need_right += 1
        else:
            if need_right == 0:
                need_left += 1  # 今出た')'と対応する'('がない。左に補充する
            else:
                need_right -= 1
    return '(' * need_left + S + ')' * need_right

N = int(input())
S = input()
print(d_insertion(N, S))

Submission status: Accepted

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

flag = True
while flag is True:
    Snum = {"(": 0, ")": 0}
    flag = False
    for s in S:
        if s == ")":
            Snum["("] -= 1
        elif s == "(":
            Snum["("] += 1

        if Snum["("] < 0:
            S = "(" + S
            flag = True
            break
    else:
        S += ")" * (S.count("(") - S.count(")"))

print(S)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = r = 0
for i in range(n):
  if s[i] == '(':
      l += 1
  else:
    if l > 0:
      l -= 1
    else:
      r += 1
for _ in range(r):
  s = "(" + s
for _ in range(l):
  s += ")"
print(s)

Submission status: Accepted

Solution code:
N = int(input())
L = input()
lst = [0]*(N)
n = 0
for i in range(N):
  if L[i] == "(":
    n += 1
  else:
    n -= 1
  lst[i] = n

# print(lst)
if min(lst) < 0:
  ans = ""
  ans += "(" * ((-1)* min(lst))
  #print("val of minlst: ", min(lst))
  ans += L
  ans += ")" * (lst[-1]+ (-1)*min(lst))
else:
  ans = L
  ans += ")" * (lst[-1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
K = S
left = 0
right = 0
for i in range(N):
    if S[i] == "(":
        left += 1
    elif S[i] == ")":
        right = 1

    if right == 1 and left == 0:
        K = "(" + K
        right = 0
    elif right == 1 and left > 0:
        right = 0
        left -= 1

S = K
left = 0
right = 0
for i in range(1,N+1):
    if S[-i] == "(":
        left = 1
    elif S[-i] == ")":
        right += 1

    if right == 0 and left == 1:
        K = K + ")"
        left = 0
    elif right > 0 and left == 1:
        right -= 1
        left = 0
print(K)

Submission status: Accepted

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

cnt = 0
o = 0
for s in S:
    if s == '(':
        cnt -= 1
    else:
        cnt += 1
        if cnt > o:
            o = cnt
c = o - cnt
o, c = max(o, 0), max(c, 0)

ans = '(' * o + S + ')' * c
print(ans)

Submission status: Accepted

Solution code:
a = int(input())
b = input()
s = b
c = 0
for i in range(a):
    if b[i] == "(":c+=1
    elif b[i] == ")" and c>0:c-=1
    else:
        s="("+s
s = s+")"*c
print(s)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
l=[]

for s in S:
    if not l:
        l.append(s)
    else:
        t=l[-1]
        if t=="(" and s==")":
            l.pop()
        else:
            l.append(s)

print("("*(l.count(")")) + S + ")"*(l.count("(")))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
cnt = 0
putLeft = 0
for si in S:
    if si=="(":
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        cnt = 0
        putLeft += 1
putRight = cnt
print("("*putLeft + S + ")"*putRight)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
count_left = 0
count_right = 0
need_left = 0 
need_right = 0
for i in range(n):
  if s[i]==")":
    count_right += 1
  else:
    count_right -= 1
  need_left = max(need_left,count_right)

for i in range(n)[::-1]:
  if s[i]=="(":
    count_left += 1
  else:
    count_left -= 1
  need_right = max(need_right,count_left)
  
print("("*need_left+s+")"*need_right)

Submission status: Accepted

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


lList = []
rList = []
diffcount = 0
cacheS = ''
for x in S:
    cacheS = cacheS + x
for i, x in enumerate(cacheS):
    if x == '(':
        lList.append(i)
        diffcount += 1
    else:
        if diffcount > 0:
            rList.append(i)
            diffcount -= 1
        else:
            S = '(' + S

if 0 < diffcount:
    for i in range(diffcount):
        S = S + ')'
else:
    for i in range(diffcount):
        S = '(' + S

print(S)

Submission status: Accepted

Solution code:
N = input()

S = raw_input()
sample = [i for i in S]

i = 0
while i < len(sample)-1:
    if sample[i] == '(' and sample[i+1] == ')':
        del sample[i],sample[i]
        i = -1
    i += 1

S = '('*sample.count(')')+S+')'*sample.count('(')
print S

Submission status: Accepted

Solution code:
N = int(input())
S = input()
putFirst = 0
putLast = 0
nowCount = 0
for i in range(N):
    if(S[i] == '('):
        nowCount += 1
    else:
        nowCount -= 1
        if nowCount < 0:
            nowCount = 0
            putFirst += 1
putLast = nowCount
print('(' * putFirst + S + ')' * putLast)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cnt = 0
dep = 10**10
for c in s:
    if c == '(':
        cnt += 1
    else:
        cnt -= 1
    dep = min(dep, cnt)
s = '(' * max(0, -dep) + s
cnt = 0
for c in s:
    if c == '(':
        cnt += 1
    else:
        cnt -= 1
s = s + ')' * cnt
print(s)

Submission status: Accepted

Solution code:
def splitter(s):
    cnt = 0
    prev = None
    ret = []
    for c in s:
        if prev is None:
            prev = c
            cnt = 1
            continue
        if c == prev:
            cnt += 1
        else:
            ret.append([cnt, prev])
            cnt = 1
            prev = c
    ret.append([cnt, prev])
    return ret

n = int(input())
s = input()
a = splitter(s)

left = 0
right = 0

if a[0][1] == ")":
    left += a[0][0]
    a.pop(0)

prev = 0
for i in a:
    if i[1] == ")":
        if prev > i[0]:
            prev -= i[0]
        else:
            left += i[0] - prev
            prev = 0
    else:
        prev += i[0]
right = prev

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

Submission status: Accepted

Solution code:
def solve(N, S):
    # print(N, ",", S)
    balance = 0
    start = 0
    for i in range(N):
        if S[i] == ")":
            if balance == 0:
                start += 1
            else:
                balance -= 1
        else:
            balance += 1
    return "(" * start + S + ")" * balance

if __name__ == "__main__":
    N = int(input())
    S = input()
    print(solve(N, S))

Submission status: Accepted

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

Submission status: Accepted

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

left = 0
right = 0
out = ""
for i in range(len(s)):
    if s[i] == "(":
        left += 1
        out += "("
    else:
        right += 1
        out += ")"
        if right > left:
            out = "(" + out
            left += 1
while left != right:
    if right > left:
        left += 1
        out = "(" + out
    else:
        right += 1
        out += ")"
print(out)

Submission status: Accepted

Solution code:
n = (int)(input())
s = input()
l = len(s)
d_l = [0]*(l+1)
for i in range(1, l+1):
    d = s[:i]
    n_open = d.count('(')
    d_l[i] = 2*n_open - i

x = min(d_l)

print('('*(-x) + s + ')'*(d_l[-1]-x))

Submission status: Accepted

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

n=0
cnt=0	#minus count
prev=0

for x in S:
	if x=="(":
		n+=1
	else:			
		n=max(n-1,0)
	if n==0:
		if prev!=1:
			cnt+=1
	prev=n


print "("*cnt+S+")"*n

Submission status: Accepted

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

stack = 0
for i in range(n):
	c = str[i]
	if(c == '('):
		stack += 1
	elif(stack == 0):
		ans = '(' + ans
	else:
		stack -= 1

for i in range(stack):
	ans = ans + ')'

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import deque

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

ans = deque()
tmp = ''
l = r = 0
for c in S:
    if c == '(':
        l += 1
        tmp += '('
    else:
        if l == 0:
            ans.appendleft('(')
            ans.append(')')
        else:
            r += 1
            tmp += ')'
            if l == r:
                ans.append(tmp)
                tmp = ''
                l = r = 0
if l > r:
    tmp += ')' * (l-r)
    ans.append(tmp)
print(''.join(ans))

Submission status: Accepted

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

# "("*L + S + ")"*R
L,R = 0,0
# 余っている "(" の個数 
rem = 0

for s in S:
    # ")"
    if s==")":
        if rem==0:
            L += 1
        else:
            R -= 1
            rem -= 1
    # "("
    else:
        R += 1
        rem += 1

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
right = 0
left = 0
for i in s:
  if i == "(":
    right += 1
  else:
    if right > 0:
      right -= 1
    else:
      left += 1
print(left*'('+s+right*')')

Submission status: Accepted

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

X = 0
ans = ''

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

    if X < 0:
        ans += '('
        X = 0

ans += S + X * ')'
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
S = input()

# カウント (:+1, ):-1
def func_cnt(str):
    cntlist = []
    tmp = 0
    for s in str:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        cntlist.append(tmp)
    
    return cntlist

# ( 不足数
cntlist = func_cnt(S)

while min(cntlist) < 0:
    S = "(" * abs(min(cntlist)) + S
    cntlist = func_cnt(S)

S = S + ")" * cntlist[-1]

print(S)

Submission status: Accepted

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

s_list = [0 for _ in range(N)]
answer = S
stack = []
for i in range(N):
    if len(stack) == 0 and S[i] == ")":
        answer = "(" + answer
    elif len(stack) != 0 and S[i] == ")":
        stack.pop()
    else:
        stack.append(S[i])

print(answer + len(stack) * ")")

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a = 0
b = 0
for i in s:
  if i == "(":
    a += 1
  else:
    if a > 0:
      a -= 1
    else:
      b += 1
print("("*b+s+")"*a)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
output = ''
lr = 0
for s in S[::-1]:
  lr += 1 if s == ')' else -1
  if lr < 0:
    output += ')'
    lr = 0
  output = s + output
print('(' * lr + output)