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()
d = [0]*(N+1) # d[i]: Sの最初のi文字における
              # "(" - ")"
for i in range(1, N+1):
    d[i] = S[:i].count("(") - S[:i].count(")")
x = min(d)
# x = 0 かつ d[N]=0ならよい
if x == 0 and d[N] == 0:
    print(S)
    exit()

ans = "("*abs(x) + S + ")"*(d[N]+abs(x))
print(ans)

Submission status: Accepted

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

for i in range(50):
  x=x.replace('()','')

l=x.count(')')
r=x.count('(')

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

for i in range(r):
  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
    elif r > 0 and i == ")":
        r -= 1
    else:
        l += 1

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
countr, countl = 0, 0

for i in range(n-1, -1, -1):
    if s[i] == ')': countr += 1
    elif countr > 0: countr -= 1
s = '('*countr+s
n = len(s)

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

print(s)

Submission status: Accepted

Solution code:
def main2():
    input()
    s = input()
    pair = [-1] * 2
    ans = s
    idx = 0
    for idx in range(0, len(s)):
        for i in range(idx, len(s)):
            if s[i] == '(':
                pair[0] = i if pair[0] == -1 else pair[0]
            elif s[i] == ')':
                pair[1] = i
                break
        if pair[0] != -1 and pair[1] != -1:
            s = s[:pair[0]] + ' ' + s[pair[0]+1:pair[1]] + ' ' + s[pair[1]+1:]
        elif pair[0] != -1 and pair[1] == -1:
            s = s[:pair[0]] + ' ' + s[pair[0]+1:]
            ans = ans + ')'
        elif pair[0] == -1 and pair[1] != -1:
            s = s[:pair[1]] + ' ' + s[pair[1]+1:]
            ans = '(' + ans
        pair = [-1] * 2
    print(ans)


if __name__ == '__main__':
    main2()

Submission status: Accepted

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

m = 0
now = 0
for i in s:
    if i == ')':
        now += 1
        if m < now:
            m = now
    else:
        now -= 1

print('('*m + s + ')'*(m + 2*s.count('(') - len(s)))

Submission status: Accepted

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

cntr = 0
for i in range(n-1, -1, -1):
    if s[i] == ')':
        cntr += 1
    elif cntr > 0:
        cntr -= 1
s = '(' * cntr + s
n = len(s)

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

print(s)

Submission status: Accepted

Solution code:
input()
s=t=input()
l,r=o="()"
exec('s=s'+'.replace(o,"")'*50)
print(l*(c:=s.count)(r)+t+r*c(l))

Submission status: Accepted

Solution code:
n=int(input())
S=input()
x=y=0
for i,s in enumerate(S):
  y=y-1 if s=='(' else y+1
  x=max(x,y)
print('('*x+S+')'*(x-y))

Submission status: Accepted

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

while "()" in S:
  S = S.replace("()","")

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

Submission status: Accepted

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

for n in range(N):
  T = T.replace("()","")

L = T.count("(")
R = T.count(")")
S = R*"("+S+L*")"
print(S)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
def run():
    N = int(input())
    S = input()
    position = 0
    l = 0
    r = 0
    for s in S:
        if s == '(':
            position += 1
        else:
            position -= 1
        if position < 0:
            l += abs(position)
            position = 0
    r += position

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

if __name__ == "__main__":
    run()

Submission status: Accepted

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

l, r = 0, 0
for i in range(n):
  if s[i] == "(":
    r += 1
  else:
    if r:
      r -= 1
    else:
      l += 1

ans = "("*l + s + ")"*r
print(ans)

Submission status: Accepted

Solution code:
icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
xmin=0
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)
    
strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Accepted

Solution code:

icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
elif len(l)<len(r):
    l.append(0)
xmin=100
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)
if xmin>0:
    xmin=0
    
strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Submission status: Accepted

Solution code:
N = int(input())
S = input().rstrip()
cnt1, cnt2 = 0, 0
for s in S:
    if s == "(":
        cnt1 += 1
    if s == ")" and cnt1 >= 1:
        cnt1 -= 1
for s in reversed(S):
    if s == ")":
        cnt2 += 1
    if s == "(" and cnt2 >= 1:
        cnt2 -= 1
print("("*cnt2 + S + ")"*cnt1)

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
S = input()

m = -min(min(accumulate(1 if c == '(' else -1 for c in S)),0)
s = sum(1 if c == '(' else -1 for c in S)

print('('*m+S+')'*(s+m))

Submission status: Accepted

Solution code:
n = int(input())
N = input()
L = 0
R = 0
num = 0
for c in N:
    if c == '(':
        num += 1
    else:
        if num:
            num -= 1
        else:
            L += 1
R = num

print('(' * L + N + ')' * R)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[2]:


l = 0
r = 0
for s in S:
    if s == "(":
        r += 1
    else:
        if r > 0:
            r -= 1
        else:
            l += 1
ans = "".join(["("*l , S, ")"*r])
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
s=hidari+S+migi


i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
t=hidari+S+migi
if len(s)==len(t):
  print(s)
elif len(s)>len(t):
  print(s)
else:
  print(t)

Submission status: Accepted

Solution code:
from collections import deque

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

l, que = 0, deque([])
for i in s:
    que.append(i)
    if i == '(':
        l += 1
    elif i == ')':
        if l == 0:
            que.appendleft('(')
            l += 1
        l -= 1
print(*que, ')' * l, sep='')

Submission status: Accepted

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

a = 0 # (
b = 0 # )
for i in range(N):
  if S[i] == '(':
    a += 1
  else:
    if a > 0:
      a -= 1
    else:
      b += 1

ans = "".join(S)
if b > 0:
  ans = "("*b + ans
if a > 0:
  ans = ans + ")"*a
print(ans)

Submission status: Accepted

Solution code:
import sys, math, re
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    S = input()
    l = [0]
    for i in range(N):
        if S[i] == '(':
            l.append(l[-1]+1)
        else:
            l.append(l[-1]-1)

    m = min(l)

    if m < 0:
        l = list(map(lambda x: x-m, l))

    print('('*l[0] + S + ')'*l[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

l, que = 0, deque([])
for i in s:
    que.append(i)
    if i == '(':
        l += 1
    if i == ')':
        if l == 0:
            que.appendleft('(')
        else:
            l -= 1
print(*que, ')' * l, sep='')

Submission status: Accepted

Solution code:
N = int(input())
S = input()
now = 0
right = 0
left = 0
add_left = 0
while now < N:
    if S[now] == '(':
        left += 1
    else:
        if left:
            left -= 1
        else:
            add_left += 1
    now += 1
for _ in range(add_left):
    print('(', end='')
print(S, end='')
for _ in range(left):
    print(')', end='')

Submission status: Accepted

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

oS = S
S = list(S)

cnt = 0
while True:
    p_cnt = cnt
    for i in range(len(S) - 1):
        if S[i] == "(" and S[i + 1] == ")":
            S.pop(i + 1)
            S.pop(i)
            cnt += 1
            break

    if cnt == p_cnt:
        break

cnt_open = 0
cnt_close = 0

for s in S:
    if s == "(":
        cnt_open += 1
    else:
        cnt_close += 1

ans = ("(" * cnt_close) + oS + (")" * cnt_open)
print(ans)

Submission status: Accepted

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

l = 0
r = 0
p = []
for i in range(n):
  if s[i] == "(": p.append("(")
  else:
    if p == []: l += 1
    else: p.pop()
r = p.count("(")
print("("*l + s + ")"*r)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    S = input()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
stack = []
for i in range(n):
    if s[i] == "(":
        stack.append("(")
    elif len(stack) == 0 or stack[-1] == ")":
        stack.append(")")
    else:
        stack.pop()
stack = sorted(stack, reverse=True)
idx = 0
while idx < len(stack):
    if stack[idx] == "(":
        break
    else:
        print("(", end="")
    idx+=1
for ch in s:
    print(ch, end="")
for i in range(idx, len(stack)):
    print(")", end="")

Submission status: Accepted

Solution code:
n, s = int(raw_input()), raw_input()
h = {'(':+1 , ')':-1}
m = 0
bal = 0
for i in range(len(s)):
	bal += h[s[i]]
	m = min(bal,m)

print '(' *abs(m) + s + ')' * (bal + abs(m))

Submission status: Accepted

Solution code:
n, s = int(raw_input()), raw_input()
h = {'(':+1 , ')':-1}
m = 0
bal = 0
for i in range(len(s)):
	bal += h[s[i]]
	m = min(bal,m)

print '(' *abs(m) + s + ')' * max(0,bal + abs(m))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
input()
s = input()
c = 0
for i in s:
    if i == "(":
        c += 1
    else:
        if c > 0:
            c -= 1
d = 0
for i in s[::-1]:
    if i ==")":
        d += 1
    else:
        if d > 0:
            d -= 1
print("("*d+s+")"*c)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()

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

    ans = "".join(["(" * L, S, ")" * R])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def Level(S):
    A=[0]
    for i in range(len(S)):
        if S[i]=="(":
            A.append(A[-1]+1)
        else:
            A.append(A[-1]-1)
    return A

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

A=Level(S)
X=-min(A)
T="("*X+S

B=Level(T)
Y=B[-1]
U=T+")"*Y

print(U)

Submission status: Accepted

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

s=s[::-1]
balance = 0
i = 0
while i < len(s):
    if s[i] == ')':
        balance+=1
    else:
        balance-=1
    if balance<0:
        s.insert(0, ')')
        balance+=1
        i+=1
    i+=1


balance = 0
i = 0
s=s[::-1]
while i < len(s):
    if s[i] == '(':
        balance+=1
    else:
        balance-=1
    if balance<0:
        s.insert(0, '(')
        balance+=1
        i+=1
    i+=1

print(''.join(s))

Submission status: Accepted

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

def add1(S):
  cum=[0]
  for i in range(len(S)):
    if S[i]=='(':cum.append(cum[-1]+1)
    else:cum.append(cum[-1]-1)
  if min(cum)>=0:return S
  out = '('*(-min(cum))
  out += S
  return out

def add2(S):
  cum=[0]
  for i in range(len(S)):
    if S[i]=='(':cum.append(cum[-1]+1)
    else:cum.append(cum[-1]-1)
      
  if cum[-1]==0:return S
  n = cum[-1]
  out = S + ')'*n
  return out

S = add1(S)
S = add2(S)
print(S)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    S = LS()
    q = deque([])
    # print(S)
    cnt = 0
    for s in S:
        if s == '(':
            cnt += 1
            q.append(s)
        else:   # ')'
            if cnt >= 1:
                q.append(s)
                cnt -= 1
            else:
                q.appendleft('(')
                q.append(s)
    for _ in range(cnt):
        q.append(')')

    # print(q)
    printlist(q, '')

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    count = 0
    for i in range(N-1, -1, -1):
        if S[i] == ")":
            count +=1
        else:
            if count:
                count -= 1
            else:
                S += ")"
    S = "("*count + S
    print(S)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    S = input()
    height = 0
    deepest = 0
    for c in S:
        if c == '(':
            height += 1
        else:
            height -= 1
        deepest = min(deepest, height)
    ans = '(' * (-deepest) + S + ')' * (height - deepest)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = 0
for i in range(n):
    ans += s[i]
    if s[i] == ")":
        if l == 0:
            ans = "(" + ans
        else:
            l -= 1
    else:
        l += 1

ans += (")"*l)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import chain
def main():
    n = int(input())
    s = tuple(input())
    cnt = 0
    cnt_ushiro = 0
    cnt_mae = 0
    for se in s:
        cnt += se == ')'
        cnt -= se == '('
        cnt_mae = max(cnt_mae, cnt)
    cnt -= cnt_mae
    if cnt < 0:
        cnt_ushiro = -cnt
    s_mae = ('(') * cnt_mae
    s_ushiro = (')') * cnt_ushiro
    r = tuple(chain(s_mae, s, s_ushiro))
    print(*r,sep="")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
d = [0]
x = 0

for i in range(len(s)):
    if s[i] == '(':
        x += 1
    else:
        x -= 1
    d.append(x)

ans = []
x = min(d)

for i in range(max(0,(-1*x))):
    ans.append('(')

for i in s:
    ans.append(i)

for i in range(max(d[len(d)-1]-x,0)):
    ans.append(')')

a = ''.join(ans)

print(a)

Submission status: Accepted

Solution code:
import re

N = int(input())
s = input()[:N]
s_check = s
s_check = re.sub('\(\)', '', s_check)

while len(s_check) > 0:
    for i in range(len(s_check)):
        if s_check[i] == ')':
            s = '(' + s
            s_check = '(' + s_check
            break
        elif s_check[i] == '(':
            break

    for i in range(len(s_check)):
        if s_check[-i-1] == '(':
            s = s + ')'
            s_check = s_check + ')'
            break
        elif s_check[-i-1] == ')':
            break

    s_check = re.sub('\(\)', '', s_check)

print(s)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    rank = 0
    q = deque()
    for s in S:
        if rank == 0:
            if s == ")":
                q.appendleft("(")
                q.append(")")
            else:
                q.append("(")
                rank += 1
        else:
            if s == ")":
                q.append(")")
                rank -= 1
            else:
                q.append("(")
                rank += 1
    while rank > 0:
        q.append(")")
        rank -= 1
    return "".join(q)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Accepted

Solution code:
import copy
N = int(input())
S = list(input())
S_ans = copy.deepcopy(S)
app = 0
q = [0]
save = 0
for i in range(N):
    if S[i] == '(':
        q.append(q[-1] + 1)
        
    else:
        q.append(q[-1] - 1)
        if q[-1] == -1:
            S_ans.insert(app + save,"(")
            app += 1
            q[-1] = 0

for i in range(q[-1]):
    S_ans.append(")")
print("".join(S_ans))

Submission status: Accepted

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

stack = []
for c in S:
    if len(stack) > 0:
        last = stack[-1]
        if last == '(' and c == ')':
            stack = stack[:-1]
            continue
    stack.append(c)

left = stack.count(')')
right = stack.count('(')

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

Submission status: Accepted

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

# (
x = 0
y = 0
for i in range(n):
    if s[i] == '(':
        x += 1

    if s[i] == ')':
        if x >= 1:
            x -= 1
        else:
            y += 1

for _ in range(x):
    s.append(')')

for _ in range(y):
    s.insert(0,'(')
ans = ''.join(s)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
nS = S
for i in range(50):
    nS = nS.replace("()", "")
r = nS.count(")")
l = nS.count("(")
print("(" * r + S + ")" * l)

Submission status: Accepted

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

while s_.count('()'):
    s_ = s_.replace('()', '')

l = s_.count(')')
r = len(s_) - l

ans = '(' * l + s + ')' * r
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys

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

    n = int(input())
    s = input()
    cnt = 0
    m = 0
    for i in range(n):
        if s[i] == '(':
            cnt += 1
        else:
            cnt -= 1
        m = min(m, cnt)
    ans = '('*(-m)+s+')'*(cnt-m)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
while True:
  c = 0
  for i in range(len(s)):
    if s[i] == "(":
      c += 1
    else:
      c -= 1
    if c < 0:
      s = "(" + s
      break
  if c > 0:
    s = s + ")"
  if c == 0:
    print(s)
    break

Submission status: Accepted

Solution code:
from collections import deque

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


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

for _ in range(left):
    s.append(")")
    

for _ in range(right):
    s.appendleft("(")

print("".join(s))

Submission status: Accepted

Solution code:
from collections import deque

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


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

for _ in range(left):
    s.append(")")
    

for _ in range(right):
    s.appendleft("(")

print("".join(s))

Submission status: Accepted

Solution code:
from collections import deque

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

reserveL = deque()
out = deque()
q = deque()

for s in S:
    if s == "(":
        reserveL.append(s)
        out.append("(")
    else:
        # print(len(reserveL))
        if len(reserveL) == 0:
            out.appendleft("(")
            out.append(")")
        else:
            out.append(")")
            reserveL.popleft()

    # print(out)

# print(out)
while reserveL:
    out.append(")")
    reserveL.popleft()
ans = ""
while out:
    ans += out.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
S = input()
que = deque(S)
l = r = 0

for s in S:
    if s == '(':
        l += 1
    else:
        r += 1
    if l < r:
        que.appendleft('(')
        l += 1
else:
    ans = "".join(que)
    if r < l:
        ans = ans + ")" * (l - r)
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

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

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    count = 0
    for i in range(N-1, -1, -1):
        if S[i] == ")":
            count +=1
        else:
            if count:
                count -= 1
            else:
                S += ")"
    S = "("*count + S
    print(S)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lp=0
rp=0
for i in range(n):
  if s[i]=='(':
    rp+=1
  else:
    rp=rp-min(rp,1)
for i in range(n-1,-1,-1):
  if s[i]==')':
    lp+=1
  else:
    lp=lp-min(lp,1)

print('('*max(0,lp)+s+max(0,rp)*')')

Submission status: Accepted

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

n = int(input())
S = input().rstrip()
b = 0
q = 0

for s in S:
    if s == '(':
        b +=1
    else:
        if b>0:
            b -= 1
        else:
            q += 1
print('('*q+S+')'*b)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=[]
minscore=0
score=0
for i in range(n):
  if s[i]=='(':
    score+=1
  else:
    score-=1
  minscore=min(minscore,score)
finalscore=score
for i in range(-minscore):
  ans.append('(')
for i in range(n):
  ans.append(s[i])
for i in range(-minscore+finalscore):
  ans.append(')')
print(''.join(ans))

Submission status: Accepted

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

flg_l = False
cnt_r = 0
cnt_l = 0

for i in range(N):
    if(S[i] == "("):
        cnt_r += 1
        flg_l = True            
    else:
        if(flg_l):
            if(cnt_r > 0):
                cnt_r -= 1
            else:
                cnt_l += 1
                flg_l = False
        else:
            cnt_l += 1
    
ans = ""

ans += ("("*cnt_l)+S+(")"*cnt_r)
print(ans)

Submission status: Accepted

Solution code:
n,s = open(0).read().split()

imp_close = 0
imp_open = 0

for char in s:
    if char == '(':
        imp_open += 1
    else:
        if imp_open:
            imp_open -= 1
        else:
            imp_close += 1

print('('*imp_close + s + ')'*imp_open)

Submission status: Accepted

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

num = [0]
for c in s:
    if c == '(':
        num.append(num[-1] + 1)
    else:
        num.append(num[-1] - 1)

for _ in range(num[0] - min(num)):
    print('(', end='')

print(s, end='')

for _ in range(num[-1] - min(num)):
    print(')', end='')

Submission status: Accepted

Solution code:
N = input()
S = input()
s = S
for i in range(50):
  S = S.replace('()','')
l = S.count(')')
r = S.count('(')
print('('*l+s+')'*r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N = int(input())
    S = input()

    solo_close_no = 0
    for i in range(N):
        if S[-i-1] == ")":
            solo_close_no += 1
        elif solo_close_no >= 1:
            solo_close_no -= 1
    
    solo_open_no = 0
    for i in range(N):
        if S[i] == "(":
            solo_open_no += 1
        elif solo_open_no >= 1:
            solo_open_no -= 1

    answer = "("*solo_close_no + S + ")"*solo_open_no
    print(answer)

if __name__ == "__main__":
    main()

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()

    right = 0
    left = 0
    for i in range(n):
        if S[i] == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    res = "(" * right + S + ")" * left
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
from collections import deque
q = deque([])
cnt = 0
for i in range(n):
    if s[i]==')':
        if cnt >0:
            cnt-=1
        else:
            q.appendleft('(')
        q.append(')')
    else:
        q.append('(')
        cnt += 1
if cnt:
    for _ in range(cnt):
        q.append(')')
print(''.join(q))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()

    ans = ""
    n_left = 0
    n_right = 0
    for s in S:
        if s == "(":
            n_left += 1
        else:
            if n_left > 0:
                n_left -= 1
            else:
                n_right += 1

    ans = "".join(("(" * n_right, S, ")" * n_left))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
S = input()
T = S.replace('()', '')
for _ in range(50):
  T = T.replace('()', '')
print('(' * T.count(')') + S + ')' * T.count('('))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = LS2()

a,b = 0,0
left = []
for i in range(N):
    if S[i] == '(':
        a += 1
    else:
        b += 1
    if a < b:
        a,b = 0,0
        left.append('(')

ANS = left + S + [')']*(a-b)

print(''.join(ANS))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
L = 0
out = []
out2 = []
for i in range(N):
    X = S[i]
    if X=="(":
        L += 1
        out.append("(")
    elif X==")":
        if L>0:
            L += -1
            out.append(")")
        else:
            out2.append("(")
            out.append(")")
for i in range(L):
    out.append(")")
print("".join(out2)+"".join(out))

Submission status: Accepted

Solution code:
n = input()
s = input()
ss = s
for i in range(50):
  s = s.replace('()','')
l = s.count(')')
r = s.count('(')
print('('*l+ss+')'*r)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
s = input()

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

s += ')'*count
        
count = 0
for i in range(n-1, -1, -1):
    if s[i] == ')':
        count += 1
    else:
        count = max(0, count-1)

s = '('*count + s
print(s)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
L=0
R=0
for i in s:
  if i==')':
    if R:R-=1
    else:L+=1
  else:
    R+=1
print('('*L+s+')'*R)