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: Wrong Answer

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

pares = S[:]

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)
        
min_num = min(pares_num)
if min_num < 0:
    pares = '(' * (-1*min_num) + pares
    

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)
#print(pares)
#print(pares_num)

zeros = [i for i, x in enumerate(pares_num) if x == 0]
if zeros:
    max_num = max(pares_num[zeros[-1]:])
    pares += ')' * max_num
else:
    max_num = max(pares_num)
    pares += ')' * max_num

print(pares)

Submission status: Wrong Answer

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

import queue
q = queue.Queue()


ans = ''
for s in pares:
    if s == '(':
        q.put(s)
    if s == ')':
        if q.empty():
            ans = '(' + ans + ')'
        else:
            q.get()
            ans += '()'
    #print(s, ans)

#print(q.qsize())
#print(q.empty())
ans = ans + q.qsize() * '(' + q.qsize() * ')'
print(ans)

Submission status: Wrong Answer

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

T = [+1 if s=='(' else -1 for s in S]

from itertools import accumulate
Tcumsum = list(accumulate(T))

i = - min(Tcumsum)

print('(' * i + S + ')' * (Tcumsum[-1]+i))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
k = [[0,0]]
flag = 0
ans = ""
for c in S:
    if c == "(":
        if flag == 0:
            k[-1][0] += 1
        else:
            flag = 0
            k.append([1,0])
    else:
        flag = 1
        k[-1][1] += 1
for i in k:
    i = max(i)
    for j in range(i):
        ans += "("
    for j in range(i):
        ans += ")"
print(ans)

Submission status: Wrong Answer

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

def solve(s):
  if not s:# empty
    return s
  left = s[0]
  right = s[-1]
  if left == ')':
    return '()' + solve(s[1:])
  if right == '(':
    return solve(s[:-1]) + '()'
  return '(' + solve(s[1:-1]) + ')'

ans = solve(S)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
cnt=0
cnt0=0
cnt1=0
tmp=0

for i in range(n):
    if tmp==")" and s[i]=="(":
        if cnt>=0:
            cnt0+=cnt
        else:
            cnt1-=cnt
        cnt=0
            
    if s[i]==")":
        cnt+=1
    else:
        cnt-=1
        
    tmp=s[i]

if cnt>=0:
    cnt0+=cnt
else:
    cnt1-=cnt

for i in range(cnt0):
    s.insert(0,"(")

for i in range(cnt1):
    s.append(")")
        
ans="".join(s)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
cnt=0
cnt0=0
cnt1=0
tmp=0

for i in range(n):
    if tmp==")" and s[i]=="(":
        if cnt>=0:
            cnt0+=cnt
        else:
            cnt1-=cnt
            
    if s[i]==")":
        cnt+=1
    else:
        cnt-=1
        
    tmp=s[i]

if cnt>=0:
    cnt0+=cnt
else:
    cnt1-=cnt

for i in range(cnt0):
    s.insert(0,"(")

for i in range(cnt1):
    s.append(")")
        
ans="".join(s)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
cnt=0
cnt0=0
cnt1=0
tmp=0

for i in range(n):
    if tmp==")" and s[i]=="(":
        if cnt>=0:
            cnt0+=cnt
        else:
            cnt1-=cnt
    if s[i]==")":
        cnt+=1
    else:
        cnt-=1
        
    tmp=s[i]

    
for i in range(cnt0):
    s.insert(0,"(")

for i in range(cnt1):
        s.append(")")
        
ans="".join(s)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
cnt0=0
cnt1=0
flg=0
tmp=0

for i in range(n):
    if tmp==")" and s[i]=="(":
        flg=abs(flg-1)
    if flg==0:        
        if s[i]==")":
            cnt0+=1
        else:
            cnt0-=1
        
    if flg==1:
        if s[i]==")":
            cnt1+=1
        else:
            cnt1-=1
    tmp=s[i]
    
    if tmp==")" and s[i]=="(":
        flg=abs(flg-1)
    
if cnt0>=0:
    for i in range(cnt0):
        s.insert(0,"(")
else:
    for i in range(-cnt0):
        s.append(")")
            
if cnt1>=0:
    for i in range(cnt1):
        s.insert(0,"(")
else:
    for i in range(-cnt1):
        s.append(")")
ans="".join(s)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
cnt0=0
cnt1=0
flg=0
tmp=0

for i in range(n):
    if tmp==")" and s[i]=="(":
        flg=abs(flg-1)
    if flg==0:        
        if s[i]==")":
            cnt0+=1
        else:
            cnt0-=1
        
    if flg==1:
        if s[i]==")":
            cnt1+=1
        else:
            cnt1-=1
    tmp=s[i]
    
    if tmp==")" and s[i]=="(":
        flg=abs(flg-1)
    
if cnt0>=0:
    for i in range(cnt0):
        s.insert(0,"(")
else:
    for i in range(-cnt0):
        s.insert(-1,")")
            
if cnt1>=0:
    for i in range(cnt1):
        s.insert(0,"(")
else:
    for i in range(-cnt1):
        s.append(")")
ans="".join(s)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
r = s.count('(')
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:
        lr -= 1
res = ''
res += '('*max(0,-lr)
res += '('*li
res = res + s + ')' * max(0, lr)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
r = s.count('(')
lr = 0
li = n
for i in range(n):
    if s[i] == '(':
        li = i
        break
for i in range(li, n):
    if s[i] == '(':
        lr += 1
    else:
        lr -= 1
res = ''
res += '('*max(0,-lr)
if li != n:
    res += '('*li
res = res + s + ')' * max(0, lr)
print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
a=[0]
for i in s[::-1]:
    if i==")":
        a.append(a[-1]+1)
    else:
        a.append(max(a[-1]-1,0))
a=a[1:][::-1]
k=""
d=0
for i in range(n):
    if a[i]-d>0:
        k+="("*(a[i]-d)
        d+=(a[i]-d)
    if s[i]=="(":
        d+=1
    if s[i]==")":
        d-=1
    k+=s[i]
print(k+")"*max(0,-a[-1]+d))

Submission status: Wrong Answer

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(lv)
r = -lv[-1] + l

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

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
t=s[0]
chk=0
d=[]
for i in s:
    if i==")"==t:
        chk-=1
    elif i=="("==t:
        chk+=1
    else:
        d.append(chk)
        t=["(",")"][i==")"]
        chk=[1,-1][i==")"]
d.append(chk)
if d[0]<0: d=[0]+d
if d[-1]>0: d.append(0)
p=sum(d)
if p<0: d[0]+=abs(p)
if p>0: d[-1]-=p
ans=""
for i in d:
    ans+=["(",")"][i<0]*abs(i)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
t=s[0]
chk=0
d=[]
for i in s:
    if i==")"==t:
        chk-=1
    elif i=="("==t:
        chk+=1
    else:
        d.append(chk)
        t=["(",")"][i==")"]
        chk=[1,-1][i==")"]
d.append(chk)
if d[0]<0: d=[0]+d
if d[-1]>0: d.append(d[-1]*-1)
p=sum(d)
if p<0: d[0]+=abs(p)
if p>0: d[-1]-=p
ans=""
for i in d:
    ans+=["(",")"][i<0]*abs(i)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
t=s[0]
chk=0
d=[]
for i in s:
    if i==")"==t:
        chk-=1
    elif i=="("==t:
        chk+=1
    else:
        d.append(chk)
        t=["(",")"][i==")"]
        chk=[1,-1][i==")"]
d.append(chk)
if d[0]<0: d=[0]+d
if d[-1]>0: d.append(d[-1]*-1)
for i in range(len(d)-1):
    if i%2==0 and d[i]+d[i+1]<0:
        d[0]+=abs(d[i]+d[i+1])
    if i%2==0 and d[i]+d[i+1]>0:
        d[i+1]=d[i]*-1
ans=""
for i in d:
    ans+=["(",")"][i<0]*abs(i)
print(ans)

Submission status: Wrong Answer

Solution code:
def trim(S, N):
    a = 0
    while S[a] == ")":
        a += 1
        if a >= N:
            break
    b = N-1
    while S[b] == "(":
        b -= 1
        if b < 0:
            break
    return a, b


def count(S, a, b):
    i = a
    c = 0
    while i <= b:
        if S[i] == "(":
            c += 1
        else:
            c -= 1
        i += 1
    return c


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

a, b = trim(S, N)
if a > b:
    print("(" * a + S + ")" * (N-b-1))
else:
    c = count(S, a, b)

    if c > 0:
        print("(" * a + S + ")" * (N-b-1+c))
    else:
        print("(" * (a-c) + S + ")" * (N-b-1))

Submission status: Wrong Answer

Solution code:
def trim(S, N):
    a = 0
    while S[a] == ")":
        a += 1
        if a >= N:
            break
    b = N-1
    while S[b] == "(":
        b -= 1
        if b < 0:
            break
    return a, b


def count(S, a, b):
    i = a
    c = 0
    while i <= b:
        if S[i] == "(":
            c += 1
        else:
            c -= 1
        i += 1
    return c


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

a, b = trim(S, N)
if a > b:
    print("(" * a + S + ")" * (N-b-1))
else:
    c = count(S, a, b)

    if c > 0:
        print("(" * a + S + ")" * (N-b-1-c))
    else:
        print("(" * (a-c) + S + ")" * (N-b-1))

Submission status: Wrong Answer

Solution code:
from collections import deque

d=deque()
N=int(input())
s=input()
d.append(s[0])
l=0
r=0
ans=s[0]
for i in range(1,N):
    ans+=s[i]
    if(len(d)==0 or d[-1]==s[i]):
        d.append(s[i])
    else:
        if(d[-1]=='('):
            r+=len(d)-1
            d.clear()
        else:
            l+=len(d)
            d.clear()
            d.append(s[i])
if(len(d)>0):
    if(d[-1]=='('):
        r+=len(d)
    else:
        l+=len(d)

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

print(ans)

Submission status: Wrong Answer

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

a=0
b=0
for x in s:
    if x=='(':
        a+=1
    else:
        b+=1
if a>b:
    print(s+')'*(a-b))
elif a<b:
    print('('*(b-a)+s)
else:
    print((n//2)*'('+s+(n//2)*')')

Submission status: Wrong Answer

Solution code:
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: Wrong Answer

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
for i in range(len(ans)):
    if ans[i] == "(":
        print(ans[i],end = "")
    else:
        break
for j in s:
    print(j,end = "")
if i != len(ans)-1:
    for j in range(i,len(ans)):
        print(ans[j],end = "")
print()
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

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]
print('(' * (-x) + s + ')' * (ds - x))

Submission status: Wrong Answer

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)
ans = ""
ans += "(" * ((-1)* min(lst))
#print("val of minlst: ", min(lst))
ans += L
ans += ")" * (lst[-1]+ (-1)*min(lst))
print(ans)

Submission status: Wrong Answer

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
print(S)
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: Wrong Answer

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


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 == 1 and left > 0:
        right = 0
        left -= 1
print(K)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ss = S.replace(')(', ') (').split()
n0 = max(0, ss[0].count(')') - ss[0].count('('))
n1 = max(0, ss[-1].count('(') - ss[-1].count(')'))
ans = '(' * n0 + S + ')' * n1
sub = ans.count(')') - ans.count('(')
if sub > 0:
    ans = '(' * sub + ans
elif sub < 0:
    ans = ans + ')' * (-sub)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ss = S.replace(')(', ') (').split()
l = 0
r = 0
for s in ss:
    a = s.count('(')
    b = s.count(')')
    l += max(0, b - a)

for s in ss[::-1]:
    a = s.count('(')
    b = s.count(')')
    r += max(0, a - b)

ans = '(' * l + S + ')' * r

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ss = S.replace(')(', ') (').split()
l = 0
r = 0
for s in ss:
    a = s.count('(')
    b = s.count(')')
    l += max(0, b - a)
    r += max(0, a - b)

ans = '(' * l + S + ')' * r

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ss = S.replace(')(', ') (').split()
ans = ''
for s in ss:
    a = s.count('(')
    b = s.count(')')
    ans = '(' * (b - a) + ans + s + ')' * (a - b)

print(ans)

Submission status: Wrong Answer

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

l_point = 0

if "(" in S:
    left_first = S.index("(")
else:
    left_first = 0

for i in range(left_first, N):
    if S[i] == "(":
        l_point += 1
    else:
        l_point -= 1



r_point = 0
T = S[::-1]

if ")" in T:
    right_first = T.index(")")
else:
    right_first = 0

for j in range(right_first, N):
    if T[j] == ")":
        r_point += 1
    else:
        r_point -= 1

migi = ")" * max(0, l_point)
hidari = "(" * max(0, r_point)
center = "".join(S)

print(hidari + center + migi)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
opn,close = 0,0
for si in S:
    if si=="(": opn += 1
    else:       close += 1
if opn>close:
    print(S + ")"*(opn-close))
else:
    print("("*(close-opn) + S)

Submission status: Wrong Answer

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

count = 0
for _ in range(N):
    if S[_] == ")":
      count += 1
    else:
      index = _
      break
      
left = "(" * count

count = 0
for _ in range(_, N):
  if S[_] == "(":
    count += 1
  else:
    count -= 1
    
if count < 0:
  left += "(" * abs(count)
  right = ""
else:
  right = ")" * count
  
print(left + S + right)

Submission status: Wrong Answer

Solution code:
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: Wrong Answer

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

n=0
cnt=0	#minus count
for x in S:
	if x=="(":
		n+=1
	else:			
		n=max(n-1,0)
	if n==0:
		cnt+=1

if n==0:
	print "("*(cnt-1)+S+")"*n
else:
	print "("*cnt+S+")"*n

Submission status: Wrong Answer

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)
                l = r = 0
if l > r:
    tmp += ')' * (l-r)
    ans.append(tmp)
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
import re
if __name__ == '__main__':
    N=int(input())
    data=input()
    diff=0
    data=data.replace('()','1')
    l=data.count('(')
    r=data.count(')')
    if l==0 and r==0:
        data=data.replace('1','()')
        print(data)
        exit(0)
    if l>r:
        diff=abs(l-r)
        for _ in range(diff):
            data=data+')'
    if r>l:
        diff=abs(l-r)
        for _ in range(diff):
            data='('+data
    if r==l :
        for _ in range(r):
            data=data+')'
        for _ in range(l):
            data='('+data
    data=data.replace('1','()')
    print(data)

Submission status: Wrong Answer

Solution code:
import re
if __name__ == '__main__':
    N=int(input())
    data=input()
    diff=0
    data.replace('()','1')
    l=data.count('(')
    r=data.count(')')
    if l==0 and r==0:
        data=re.sub('1','()',data)
        print(data)
    if l>r:
        diff=abs(l-r)
        for _ in range(diff):
            data=data+')'
    if r>l:
        diff=abs(l-r)
        for _ in range(diff):
            data='('+data
    if r==l :
        for _ in range(r):
            data=data+')'
        for _ in range(l):
            data='('+data
    data=re.sub('1','()',data)
    print(data)

Submission status: Wrong Answer

Solution code:
import re
if __name__ == '__main__':
    N=int(input())
    data=input()
    diff=0
    data.replace('()','1')
    l=data.count('(')
    r=data.count(')')
    if l==0 and r==0:
        data=re.sub('1','()',data)
        print(data)
    if l>r:
        diff=abs(l-r)
        for _ in range(diff):
            data=data+')'
    if r>l:
        diff=abs(l-r)
        for _ in range(diff):
            data='('+data
    if r==l :
        for _ in range(r):
            data=data+')'
        for _ in range(l):
            data='('+data
    data=re.sub('1','()',data)
    print(data)

Submission status: Wrong Answer

Solution code:
import re
if __name__ == '__main__':
    N=int(input())
    data=input()
    diff=0
    data.replace('()','1')
    l=data.count('(')
    r=data.count(')')

    if l>r:
        diff=abs(l-r)
        for _ in range(diff):
            data=data+')'
    if r>l:
        diff=abs(l-r)
        for _ in range(diff):
            data='('+data
    data=re.sub('1','()',data)
    print(data)

Submission status: Wrong Answer

Solution code:
import re
if __name__ == '__main__':
    N=int(input())
    data=input()
    diff=0
    print(data)
    data.replace('()','1')
    print(data)
    l=data.count('(')
    r=data.count(')')

    if l>r:
        diff=abs(l-r)
        for _ in range(diff):
            data=data+')'
    if r>l:
        diff=abs(l-r)
        for _ in range(diff):
            data='('+data
    data=re.sub('1','()',data)
    print(data)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
left=0
right=0
t=0
for i in range(n):
    if s[i]=="(":
        t+=1
    else:
        right+=1
        left+=t
        t=0
s="("*max(0,right-left)+s+")"*(t+max(0,left-right))
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
c = 0
sl = 0
lli =[]
rli =[]
k = 0
j = 0
for i in range(n):
    if i == 0:
        if s[i] == "(":
            lli.append(1)
            j = 1
        else:
            sl += 1
            k = 1
    elif s[i] == "(":
        k = 0
        if c == 1 or j == 1:
            lli[-1] += 1
            j = 0
        else:
            lli.append(1)
        c = 1
    else:
        if k == 1:
            sl += 1
        elif c == 2:
            if lli[-1] > 0:
                lli[-1] -= 1
            else:
                rli[-1] += 1
        else:
            rli.append(0)
            lli[-1] -= 1
        c = 2

if sum(rli) + sl > 0 and sum(lli) > 0:
    print("(" * (sum(rli) + sl) + s + ")" * sum(lli))
elif sum(rli) + sl <= 0 and sum(lli) > 0:
    print(s + ")" * sum(lli))
elif sum(rli) + sl > 0 and sum(lli) <= 0:
    print("(" * (sum(rli) + sl) + s)
else:
    print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
c = 0
sl = 0
lli =[]
rli =[]
k = 0
for i in range(n):
    if i == 0:
        if s[i] == "(":
            lli.append(1)
        else:
            sl += 1
            k = 1
    elif s[i] == "(":
        k = 0
        if c == 1:
            lli[-1] += 1
        else:
            lli.append(1)
        c = 1
    else:
        if k == 1:
            sl += 1
        elif c == 2:
            if lli[-1] > 0:
                lli[-1] -= 1
            else:
                rli[-1] += 1
        else:
            rli.append(0)
            lli[-1] -= 1
        c = 2

if sum(rli) + sl > 0 and sum(lli) > 0:
    print("(" * (sum(rli) + sl) + s + ")" * sum(lli))
elif sum(rli) + sl <= 0 and sum(lli) > 0:
    print(s + ")" * sum(lli))
elif sum(rli) + sl > 0 and sum(lli) <= 0:
    print("(" * (sum(rli) + sl) + s)
else:
    print(s)

Submission status: Wrong Answer

Solution code:
N=int(input().strip())
S=input().strip()
x=[]
lc=0
rc=0
for i in range(len(S)):
    if S[i]=='(':
        lc+=1
    elif S[i]==')':
        rc+=1
    x.append(lc-rc)

xn=min(x)
d=lc-rc

ans='('*(-xn)+S+')'*(d-xn)

print(ans)

Submission status: Wrong Answer

Solution code:
a = int(input())
ar = list(input())
b = 0
c = 0
z = 0
for l in ar:
    if l == ")":
        z += 1
    else:
        break
for i in range(z):
    ar.insert(0,"(")
for r in ar:
    if r == "(":
        b += 1
    else:
        c += 1
if b > c:
    d = b - c
    for i in range(d):
        ar.append(")")
else:
    d = c - b
    for i in range(d):
        ar.insert(0,"(")
print("".join(ar))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
i = 0
k = 0
while i < len(s):
  if s[i] == "(":
    k += 1
    i += 1
  else:
    if k > 0:
      k -= 1
      i += 1
    else:
      s = s[:i] + "(" + s[i:]
print(s+")"*k)

Submission status: Wrong Answer

Solution code:
def insertion(S):
    Sc = S
    Scc = Sc.replace("()", "")
    while Scc != Sc:
        Sc = Scc
        Scc = Scc.replace("()", "")

    # Sc は ((((... or ))))... or ...))))((((...
    print(Sc)
    if len(Sc) == 0:
        Sl, Sr = "", ""
    elif Sc[0] != Sc[-1]:
        pos = Sc.find(")(")
        Sl = insertion(Sc[:pos+1])[0]
        Sr = insertion(Sc[pos+1:])[2]
    elif Sc[0] == '(':
        Sl = ""
        Sr = ')' * len(Sc)
    else:
        Sl = '(' * len(Sc)
        Sr = ""

    return Sl, S, Sr

N = int(input())
s = insertion(input())
print(s[0]+s[1]+s[2])

Submission status: Wrong Answer

Solution code:
def insertion(S):
    Sc = S
    Scc = Sc.replace("()", "")
    while Scc != Sc:
        Sc = Scc
        Scc = Scc.replace("()", "")

    # Sc は ((((... or ))))... or ...))))((((...
    # print(Sc)
    if len(Sc) == 0:
        pass
    elif Sc[0] != Sc[-1]:
        pos = Sc.find(")(")
        S = insertion(S[:pos+1]) + insertion(S[pos+1:])
    elif Sc[0] == '(':
        S += ')' * len(Sc)
    else:
        S = '(' * len(Sc) + S

    return S

N = int(input())
print(insertion(input()))

Submission status: Wrong Answer

Solution code:
N = input()
s = input()
s1 = s
s2 = ''
while s1 != s2: 
    s2 = s1
    s1 = s1.replace('()','')
print(s1)
s2 = s1.replace('(','')

print(len(s2)*'(' + s + (len(s1)-len(s2))*')')

Submission status: Wrong Answer

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

look = 0
left = 0
right = 0
insertion = 0

while look < len(s):
    if s[look] == "(":
        right += 1
    elif s[look] == ")":
        left += 1
    if right == left:
        insertion = look
    elif left > right:
        s.insert(insertion,"(")
        right += 1
        look += 1
    look += 1

if right > left:
    for i in range(right-left):
        s.append(")")
for i in range(len(s)):
    if i != len(s) -1:
        print(s[i],end = "")
    else:
        print(s[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
x=[]
y=0
for i in range(n):
    if s[i]=="(":
        x.append("(")
        y+=1
    elif y>0:
        x.append(")")
        y-=1
    else:
        x.append(")")
        x=["("]+x
print("".join(x))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
S = input()
open_cnt = 0
cnt = 0
open_flg = True
for i in range(N):
    if S[i] == '(':
        if not open_flg:
            cnt = 0
        cnt += 1
    else:
        open_flg = False
        cnt -= 1
        if cnt < 0:
            open_cnt += 1
cnt = 0
close_flg = True
close_cnt = 0
for i in range(N-1, -1, -1):
    if S[i] == ')':
        if not close_flg:
            cnt = 0
        cnt += 1
    else:
        close_flg = False
        cnt -= 1
        if cnt < 0:
            close_cnt += 1
print('(' * open_cnt + S + ')' * close_cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
right = 0
left = 0
look = 0
insertion = 0

while look < len(s):
    if s[look] == '(':
        right += 1
    else:
        left += 1
    if right < left:
        s.insert(insertion,'(')
        right += 1
        look += 1
    elif right == left:
        insertion = look
    look += 1

if right > left:
    for i in range(right-left):
        s.append(')')

for i in range(len(s)):
    if i != len(s)-1:
        print(s[i],end = "")
    else:
        print(s[i])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

LL, LR, RL, RR = 0, 0, 0, 0
for i in range(N//2):
    if S[i] == "(":
        LL += 1
    else:
        LR += 1
for i in range(N//2, N):
    if S[i] == "(":
        RL += 1
    else:
        RR += 1
if LL > RR:
    ans = "(" * LR + S + ")" * (RL + LL - RR)
else:
    ans = "(" * (LR + RR - LL) + S + ")" * RL
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ans = ""
hidari = 0
migi = ""
for i in range(n):
    if s[i] == "(":
        ans += s[i]
        hidari += 1
    else:
        hidari = 0
        if i < n - 1:
            ans += "("
            migi += ")"
            if s[i + 1] == "(":
                ans += migi
                migi = ""
        else:
            ans += migi + ")"
ans += ")" * hidari
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
b = list(a.replace("()",""))

left = b.count(")")
right = b.count("(")
l = []
r = []

for i in range(left):
    l.append("(")

for i in range(right):
    r.append(")")

ans = ["".join(l), a, "".join(r)]
print("".join(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
a = lambda q: q.count('(')-q.count(')')

while True:
    flag = True
    for i in range(len(s)):
        if a(s[:i])+a(s[i:])!=0:
            flag = False
            if a(s[:i]) > -a(s[i:]):
                s = s + ')'
            else:
                s = '(' + s
            break
    if flag:
        print(s)
        break

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

#N = 4
#S = "(()"

S_list = list(S)

if "(" in S_list:    
    start_min = S_list.index("(")
else:
    start_min = N
    
if ")" in S_list:
    last_max = S_list[::-1].index(")")
else:
    last_max = N
    
for _ in range(start_min):
    S = "(" + S
for _ in range(last_max):
    S = S + ")"    

ct = Counter(S)
start_num = ct["("]
last_num = ct[")"]
diff = start_num - last_num
if diff>0:
    for i in range(diff):
        S = S + ")"
elif diff<0:
    for i in range(-diff):
        S = "(" + S


print(S)