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

dic = {'(':1, ')':-1}

rlt = ''
cnt = 0
for s in S:
  cnt += dic[s]
  rlt += s
  if cnt < 0:
    rlt = '(' + rlt
    cnt = 0
  
if cnt > 0:
  rlt += ')'*cnt
  
print(rlt)

Submission status: Accepted

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

l, r = 0, 0
p, m = 0, 0
for i in range(N):
  if S[i] == "(":
    l += 1
  else:
    r += 1
  if l < r:
    p += 1
    l += 1

m = l - r

for i in range(p):
  print("(", end = "")
print(S, end ="")
for i in range(m):
  print(")", end = "")

Submission status: Accepted

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

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
ans = ["("]*c1 + s + [")"]*c0
print("".join(ans))

Submission status: Accepted

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

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
z0 = c1
s = s[::-1]
c0 = 0
c1 = 0
for i in range(n):
    if s[i] == ")":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
z1 = c1
s = s[::-1]
ans = ["("]*z0 + s + [")"]*z1
print("".join(ans))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
A=0 #(
B=0 #)

for s in S:
    if s=='(':
        A+=1
    elif s==')' and A>0:
        A-=1
    else:
        B+=1

print('('*B+S+')'*A)

Submission status: Accepted

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

a = ""

stack = []

for i in range(len(s)):
    if s[i] == "(":
        stack.append("(")
        a += "("
    elif s[i] == ")" and len(stack) == 0:
        stack.append(")")
        a += ")"
    elif s[i] == ")" and stack[-1] == ")":
        stack.append(")")
        a += ")"
    else:  # s[i] == ")" and stack[-1] == "("
        stack.pop(-1)
        a += ")"

while len(stack) > 0:
    if stack[len(stack) - 1] == ")":
        e = len(stack) - 1
        s = e
        while s - 1 >= 0 and stack[s - 1] == ")":
            s -= 1
        a = "(" * (e - s + 1) + a
        stack = stack[:s]
    elif stack[len(stack) - 1] == "(":
        e = len(stack) - 1
        s = e
        while s - 1 >= 0 and stack[s - 1] == "(":
            s -= 1
        a = a + ")" * (e - s + 1)
        stack = stack[:s]

print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
S = input()
lc = 0
rc = 0
for s in S:
    if s=='(':
        rc += 1
    else:
        if rc:
            rc -= 1
        else:
            lc += 1
print('('*lc+S+')'*rc)

Submission status: Accepted

Solution code:
_,S,l,r=input(),input(),'(',')'
t=S
while t.count(l+r):
 t=t.replace(l+r,'')
print(l*t.count(r)+S+r*t.count(l))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    S = in_s()

    ts = S
    while ts.count('()'):
        ts = ts.replace('()', '')

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
_ = input()
S = input()

needs_right = 0
needs_left = 0

for c in S:
    if c == '(':
        needs_right += 1
    else:
        if needs_right == 0:
            needs_left += 1
        else:
            needs_right -= 1

print('(' * needs_left + S + ')' * needs_right)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
input();s=t=input()
while'()'in t:t=t.replace('()','')
c=t.count;print('('*c(')')+s+')'*c('('))

Submission status: Accepted

Solution code:
input()
s=t=input()
while '()' in t: t=t.replace('()','')
c=t.count
print('('*c(')')+s+')'*c('('))

Submission status: Accepted

Solution code:
_,s=input(),input()
t=0
for c in s:
  if c=='(': t+=1
  else: t-=1
  if t<0: s='('+s; t+=1
print(s+')'*t)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=r=0
for c in s:
  if c=='(': l+=1
  else: r+=1
  if r>l: s='('+s; l+=1
print(s+')'*(l-r))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = collections.deque()

    for i in S:
        if i == '(':
            stk.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
            else:
                ans.appendleft('(')
        ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = collections.deque()

    for i in S:
        if i == '(':
            stk.append(i)
            ans.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
                ans.append(i)
            else:
                ans.appendleft('(')
                ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = []

    for i in S:
        if i == '(':
            stk.append(i)
            ans.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
                ans.append(i)
            else:
                ans.insert(0, '(')
                ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools
import functools
import  operator

def solve():
    n = int(input())
    s = input()
    l, r = 0, 0
    for i in s:
        if i == "(":
            r += 1
        else:
            if r != 0:
                r -= 1
            else:
                l += 1
    ans = "("*l + s + ")"*r
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
while True:
    lv = 0
    lmin = len(S)
    for i in range(len(S)):
        if S[i]=="(":
            lv += 1
        else:
            lv -= 1
        lmin = min(lmin,lv)
    if lmin<0:
        S = "("*(-lmin)+S
    else:break
lv = 0
for i in range(len(S)):
    if S[i]=="(":
        lv += 1
    else:
        lv -= 1

if lv>0:
    S = S+")"*lv
print(S)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = s
while s.count("()")>0:
    s = s.replace("()", "")
cnt_l = s.count(")")
cnt_r = s.count("(")
ans = cnt_l * "(" + ans
ans += cnt_r * ")"
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
X=0
S=input()
T,U='',''
for i in range(N):
  if S[i]=='(':
    X+=1
  else:
    if X==0:
      T+='('
    else:
      X-=1
U=')'*X
print(T+S+U)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,S = open(0).read().split()
o = 0
c = 0
pre = 0
temp_o = 0
for b in S:
    if b == '(':
        o += 1
        temp_o += 1
    else:
        c += 1
        if temp_o == 0:
            pre += 1
        else:
            temp_o -= 1
suf = max(0,pre+o-c)
ans = ('('*pre) + S + (')'*suf)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    s = input()

    l = 0
    r = 0

    for char in s:
        if char == "(":
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    print("(" * r + s + ")" * l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
writtenC = 0
writtenD = 0
for i in range(n):
    if s[i] == ")" and writtenC == 0:
        writtenD += 1
    elif s[i] == ")":
        writtenC -= 1
    else:
        writtenC += 1
print("(" * writtenD + s + ")"*writtenC)

Submission status: Accepted

Solution code:
N = int(input())
T = input()
S = list(T)
G = True
while G:
    G = False
    for i in range(1, len(S)):
        if S[i - 1] == '(' and S[i] == ')':
            S.pop(i)
            S.pop(i - 1)
            G = True
            break
for s in S:
    if s == '(':
        T = T + ')'
    else:
        T = '(' + T
print(T)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
S = input()

l = 0
r = 0

for x in S:
	if x == "(":
		r += 1
	elif x == ")":
		if 0 < r:
			r -= 1
		else:
			l += 1

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
S = input()

l = 0
for x in S[::-1]:
	if x == ")":
		l += 1
	elif x == "(" and 0 < l:
		l -= 1
r = 0
for x in S:
	if x == "(":
		r += 1
	elif x == ")" and 0 < r:
		r -= 1

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
S = input()
left = 0
right = 0
for i in range(N):
    if S[i] == '(':
        right += 1
    if S[i] == ')':
        if right >= 1:
            right -= 1
        else:
            left += 1
print('('*left + S + ')'*right)

Submission status: Accepted

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

d=[0]*n

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

x=min(d)

s='('*(-x) + s

d2=[0]*(len(s))
cnt=0
for i in range(len(s)):
    if s[i]=='(':
        cnt+=1
    else:
        cnt-=1
    d2[i]=cnt

s=s+')'*d2[-1]

print(s)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = deque([])
emp = deque([])
for s in S[::-1]:
    if s == ")":
        ans.append('(')
    else:
        if ans:
            ans.pop()
        else:
            emp.append(')')
ans = list(ans)
emp = list(emp)
print("".join(ans)+S+"".join(emp))

Submission status: Accepted

Solution code:
import sys


#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')


def main():
	n=II()
	s=input()
	ss=s
	for _ in range(100):
		s=s.replace("()","")
	ans="("*s.count(")")+ss+")"*s.count("(")
	print(ans)
	
	
	





	

if __name__=="__main__":
	main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')


def main():
	n=II()
	s=input()
	
	A=[]
	if s[0]==")":
		A.append(0)
	s+="0"
	cnt=1
	for i in range(n):
		if s[i]==s[i+1]:
			cnt+=1
		else:
			A.append(cnt)
			cnt=1
	#print(A)
	
	l=0
	r=0
	now=0
	for i in range(len(A)):
		#print(r)
		if i%2:
			r+=2*min(A[i],now)
			l+=max(A[i]-now,0)
			now=max(now-A[i],0)
		else:
			now+=A[i]
	#print(l,n-l-r)
	
	ans="("*l+s[:-1]+")"*(n-l-r)
	print(ans)
	
	
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

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

left = ''
right = ''

skip_idx = []
for idx, s in enumerate(S):
    if idx in skip_idx:
        continue
    if s == ')':
        left += '('
    else:
        # print(j)
        skip_flag = 0
        for n in range(idx+1, N):
            if n in skip_idx:
                continue
            if S[n] == ')':
                skip_idx.append(n)
                skip_flag = 1
                break
        if not skip_flag:
            right += ')'
    # print(idx, s, left, right, skip_idx)

print(left+S+right)

Submission status: Accepted

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

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

Submission status: Accepted

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

cd = []
q = []
for s in S:
    if q and q[-1]=="(":
        if s==")":
            q.pop()
        else:
            q.append(s)
    else:
        q.append(s)
sl = []
sr = []
for s in q:
    if s==")":
        sl.append("(")
    else:
        sr.append(")")
print("".join(sl)+S+"".join(sr))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N = int(input())
    T = input()
    S = []
    for s in T:
        if s == '(':
            S.append(1)
        else:
            S.append(-1)
    S = list(accumulate(S))
    # print(S)
    minS = min(S)
    if minS < 0:
        for i in range(N):
            S[i] -= minS
    print('('*max(0,-minS) + T + ')'*S[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

cd = []
q = []
for s in S:
    if q and q[-1]=="(":
        if s==")":
            q.pop()
        else:
            q.append(s)
    else:
        q.append(s)
sl = []
sr = []
for s in q:
    if s==")":
        sl.append("(")
    else:
        sr.append(")")

print("".join(sl)+S+"".join(sr))

Submission status: Accepted

Solution code:
n = int(input())
data = [c for c in input()]
stack = []
ans = ''
for c in data:
    if c == '(':
        stack.append(c)
        ans += '('
    else:
        if len(stack) == 0 or stack.pop() != '(':
            ans = '(' + ans + c
        else:
            ans += ')'
ans += ')'*len(stack)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = input()
A = deque([])
l = 0
r = 0
for i in range(n):
  if s[i]=='(':
    A.append(s[i])
    l += 1
  else:
    if l!=0:
      A.append(s[i])
      l -=1
    else:
      A.appendleft("(")
      A.append(s[i])

for j in range(l):
  A.append(")")
  
print("".join(A))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
x, y, z=0, 0, 0
for i in range(N):
  if S[i]=='(':
    x+=1
  else:
    y+=1
  z=min(z, x-y)
print('('*-z+S+')'*max(0, x-z-y))

Submission status: Accepted

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

res = ""
st = []
for s in S:
    if s == "(":
        st.append("(")
        res += "("
    else:
        if st:
            st.pop()
            res += ")"
        else:
            res = "(" + res + ")"

print(res + ")" * len(st))

Submission status: Accepted

Solution code:
N = 6
S = ')))())'


# N = 8
# S = '))))(((('

# N = 3
# S = '())'

# N = 9
# S = '(())()()('

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

def calculate(n, str):

    finalStr = ''
    while True:
        point = 0
        remainStr = ''
        for i in range(len(str)):
            if i > 0:
                if (str[i-1] == '(') and (str[i] == ')'):
                    point += 1
                    continue

            if i < (n - 1):
                if (str[i] == '(') and (str[i+1] == ')'):
                    point += 1
                    continue

            remainStr += str[i]

        str = remainStr
        n = len(str)
        if point == 0:
            finalStr = remainStr
            return finalStr
            break







res = calculate(N, S)

for i in range(len(res)):
    if res[i] == '(':
        S = S + ')'

    if res[i] == ')':
        S = '(' + S

print(S)
# print(result)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
stack = []
cntLeft = 0
cntRight = 0
for ss in s:
    if ss == '(':
        stack.append('(')
    else:
        if len(stack) > 0:
            stack.pop()
        else:
            cntLeft += 1
cntRight = len(stack)
ans = ''
for i in range(cntLeft):
    ans += '('
ans += s
for i in range(cntRight):
    ans += ')'
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())
    s_s = list(input())

    # work_s = str(s)

    for i in range(101):
        j = 0
        c = 0
        for cnt, s in enumerate(s_s):
            if s == "(":
                c += 1
            else:
                j += 1
            if c < j:
                s_s = ["("] + s_s
                break
            if cnt == len(s_s) - 1 and c > j:
                s_s = s_s + [")"]

    print("".join(s_s))
        # work_s = work_s.replace("()", "1")
        #
        # if i == 0:
        #     for j in range(100):
        #         work_s = work_s.replace("(X)", "X")
        # else:
        #     work_s = work_s.replace("(X)", "X")

        # テストクラス


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
())"""
        output = """(())"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6
)))())"""
        output = """(((()))())"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """8
))))(((("""
        output = """(((())))(((())))"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    S = input()
    left_shortage = 0
    now = 0
    for s in S:
        if s == "(":
            now += 1
        else:
            now -= 1
            left_shortage = min(now, left_shortage)

    right_shortage = 0
    now = 0
    for s in S[::-1]:
        if s == ")":
            now += 1
        else:
            now -= 1
            right_shortage = min(now, right_shortage)

    print("("*-left_shortage + S + ")"*-right_shortage)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
diff = [0] * (N + 1)
for i in range(N):
    if S[i] == "(":
        diff[i + 1] = diff[i] + 1
    else:
        diff[i + 1] = diff[i] - 1
min_diff = min(diff)
print("(" * -min_diff + S + ")" * (diff[N] - min_diff))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = list(input())

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

S = ['(']*c + S + [')']*(left+c-right)
print(''.join(S))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l_cnt = 0
r_cnt = 0
l_ans = 0
for i in s:
    if i == ')':
        if l_cnt:
            l_cnt -= 1
        else:
            l_ans += 1
    else:
        l_cnt += 1

print(l_ans*'(' + s + l_cnt*')')

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
ins=0
app=0
for i in range(n):
    if s[i]=='(':
        app += 1
    else:
        if app>0:
            app -= 1
        else:
            ins += 1
inL=['(']*ins
app=[')']*app
ans=inL+s+app
print(''.join(ans))

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
p = 0
q = 0
for i in range(n):
    if s[i] == ")":
        if q == 0:
            p += 1
        else:
            q -= 1
    else:
        q += 1
print("("*p+s+")"*q)

Submission status: Accepted

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

    l, r = 0, 0

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    S = list(input())
    nopen = 0
    addleft = 0
    addright = 0
    for s in S:
        if s == "(":
            nopen += 1
        else:
            if nopen == 0:
                addleft += 1
            else:
                nopen -= 1
    addright = nopen
    print("("*addleft+"".join(S)+")"*addright)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
l = r = lv = rv = 0
for i in range(n):
    if s[i]=='(':
        l += 1
    elif l>0:
        l -= 1
    else:
        rv += 1
for i in range(n-1,-1,-1):
    if s[i]==')':
        r += 1
    elif r>0:
        r -= 1
    else:
        lv += 1
print('('*rv+s+')'*lv)

Submission status: Accepted

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

L = 0  # 左かっこの数
R = 0  # 右かっこの数
cnt = 0  # 左かっこ(の数に対応した、あるべき右かっこ)の数

for i in s:
    if i == "(":
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:  # あるべき右かっこの数が０以下のとき、足りてないのは左かっこ
            L += 1
R = cnt

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

Submission status: Accepted

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

need_left = 0
pointer = 0

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

res = ""
for i in range(need_left):
    res += "("
res += s

for i in range(pointer):
    res += ")"

print(res)

Submission status: Accepted

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

ans = S
cnt = 0
now = ""
for s in S:
    now = s
    if s == "(":
        cnt += 1
    elif s == ")":
        cnt -= 1
    if cnt == -1:
        ans = "(" + ans
        cnt = 0
if cnt > 0:
    ans = ans + ")"*cnt

print(ans)

Submission status: Accepted

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

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

print(l_cnt * "(" + s + r_cnt * ")")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
s=ss()

cc = 0
res = s
for i in s:
    if i == "(":
        cc += 1
    elif i == ")":
        cc -= 1
        if cc < 0:
            res = "(" + res
            cc = 0

res += ")" * cc
print(res)