Problem:


Score : 400 points

Problem Statement

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

Here, a correct bracket sequence is defined as follows:  

() is a correct bracket sequence.

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

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

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

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

Constraints

The length of S is N.

1 ≤ N ≤ 100

S consists of ( and ).

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

3
())

Sample Output 1

(())

Sample Input 2

6
)))())

Sample Output 2

(((()))())

Sample Input 3

8
))))((((

Sample Output 3

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



Sample input:
3
())


Sample output:
(())

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

N = ni()
S = ns().strip()

d = 0
mind = 0

for i in range(len(S)):
    if(S[i] == '('):
        d += 1
    else:
        d -= 1
    mind = min(mind,d)
print ('('*(-mind) + S + ')'*(d-mind))

Submission status: Accepted

Solution code:
N = int(raw_input())
a = raw_input()

b = list(a)
check = 0
j = 0
k = 0
for i in range(N):
	if b[i] == "(":
		check = check + 1
	else:
		check = check - 1
	
	if check < 0:
		j += 1
		check = check + 1
for i in range(j):
	b = ["("] + b

for i in range(check):
	b = b + [")"]
	k += 1
import six
for i in range(N+j+k):
	six.print_(b[i],end = "")

Submission status: Accepted

Solution code:
n = int(input())
str = input()
 
r = 0
l = 0
i = 0
 
while i < n:
    if str[i] == '(':
        l += 1
        i += 1
    elif str[i] == ')' and l == 0:
        str = '(' + str
        n += 1
        i += 2
    else:
        l -= 1
        i += 1
 
if l > 0:
    while l > 0:
        str = str + ')'
        l -= 1
 
print(str)

Submission status: Accepted

Solution code:
n = input()
str = raw_input()

r = 0
l = 0
i = 0

while i < n:
    if str[i] == '(':
        l += 1
        i += 1
    elif str[i] == ')' and l == 0:
        str = '(' + str
        n += 1
        i = 0
    else:
        l -= 1
        i += 1

if l > 0:
    while l > 0:
        str = str + ')'
        l -= 1

print str

Submission status: Accepted

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

lc=0
rc=0
for brc in s:
    if brc=='(':
        lc+=1
    elif brc==')':
        if lc>0:
            lc-=1
        else:
            rc+=1
            
retVal=""
for i in range(rc):
    retVal+='('
retVal+=s
for i in range(lc):
    retVal+=')'
print(retVal)

Submission status: Accepted

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

head = 0
tail = 0

for i in S:
    if i == "(":
        head += 1
    elif head > 0:
        head -= 1
    else:
        tail += 1

res = tail * "(" + S + head * ")"
print(res)

Submission status: Accepted

Solution code:
import copy


def get_completed(s):
    ans = copy.deepcopy(s)

    not_close = 0
    not_open = 0

    for c in s:
        if c == '(':
            not_close += 1

        if c == ')':
            if not_close > 0:
                not_close -= 1
            else:
                not_open += 1

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

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

    return ans


if __name__ == '__main__':
    N = input()
    S = input()

    print(get_completed(S))

Submission status: Accepted

Solution code:
n = input()
s = input()
count = 0
countl = 0
for c in s:
    if c=='(':
        count += 1
    else:
        count -= 1
    if count < 0:
        countl += 1
        count = 0
count = 0
countr = 0
for c in s[::-1]:
    if c=='(':
        count -= 1
    else:
        count += 1
    if count < 0:
        countr += 1  
        count = 0
print('('*countl + s + ')'*countr)

Submission status: Accepted

Solution code:

# coding: utf-8

# In[38]:

number = int(input())
strings = input()


# In[39]:

while True:
    counter = 0

    for s in strings:
        if s == "(":
            counter += 1
        else:
            if counter > 0:
                counter -= 1
            else:
                strings = "(" + strings
                counter = -1
                break
        
    if counter > 0:
        strings = strings + ")" * counter
        
    if counter == 0:
        break

print(strings)


# In[ ]:

Submission status: Accepted

Solution code:
import sys


if __name__ == "__main__":
    N = raw_input()
    S = raw_input()

    bra = 0
    ket = 0
    pair = 0
    # ket = 0
    for s in S:
        if s == '(':
            bra += 1
        else:
            if bra > 0:
                bra -= 1
                pair +=1
            else:
                ket += 1
    print '(' * ket + S + ')'*bra

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
x = int(input())
y = input()

z = y

while z.find("()") != -1:
    z = z.replace("()","")

a = z.count("(")
b = z.count(")")

ans = y

for i in range(a):
    ans = ans + ")"

for i in range(b):
    ans = "(" + ans

print(ans)

Submission status: Accepted

Solution code:
#Python

N = input()
S = raw_input()

#print N
#print S
chars=list(S)
#print chars

sum=0
for i in chars:
	if i == "(":
		sum+=1
		#print sum
	elif i== ")":
		sum-=1
		#print sum
		if sum<0:
			S="("+S
			sum=0

S=S+")"*sum

print S

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=0
b=0
p=0
for i in range(len(s)):
  if s[i]=="(":
     a+=1
  if s[i]==")":
     b+=1
     a-=1
     if a<0:
       p+=1
       a=0
print("("*p+s+")"*a)

Submission status: Accepted

Solution code:
N = input()
ss = raw_input()
s=ss.split("()")

while len(s)>1:
    s="".join(s)
    #print(s)
    s=s.split("()")

a=""
b=""

s=s[0]
N=len(s)



for i in range(N):
    if s[i]=="(":
        a+=")"
    if s[i]==")":
        b+="("

print(b+ss+a)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

N, = map(int, sys.stdin.readline().rstrip().split())
S = sys.stdin.readline().rstrip()

def is_fullfilled(in_str):
    LR = 0
    for c in in_str:
        if LR < 0:
            return False
        if c == "(":
            LR += 1
        else:
            LR -= 1
    if LR == 0:
        return True
    else:
        return False


LR = 0
for c in S:
    if c == "(":
        LR += 1
    else:
        LR -= 1

while LR < 0:
    S = "(" + S
    LR += 1
while LR > 0:
    S = S + ")"
    LR -= 1

while not is_fullfilled(S):
    #print(S)
    S = "(" + S + ")"

print(S)

exit(0)

Submission status: Accepted

Solution code:
N=input()
brac = raw_input()
ans = brac

while '()' in brac:
	brac=brac.replace('()','')

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

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

Submission status: Accepted

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

n = 0
m = 0
for s in S:
	if s == '(':
		n += 1
	else:
		n -= 1
	m = min(n, m)

l = abs(m)
r = n + l

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

Submission status: Accepted

Solution code:
input()

s = raw_input().strip()

l = "("
r = ")"

l_c = 0
r_c = 0
for c in s:
    if c == l:
        l_c+=1
    elif c == r:
        if l_c>0:
            l_c-=1
        else:
            r_c+=1
            
print "(" * r_c + s + ")" * l_c

Submission status: Accepted

Solution code:
input()
gt =input()
gtt = gt
for i in range(100):
    gt = gt.replace("()","",2)

num1 = gt.count("(")
num2 = gt.count(")")
print("("*num2+gtt+")"*num1)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
open=0
output=S
for c in S:
    if c=="(":
        open=open+1

    else:
        if open>0:
            open=open-1
        else:
            output="("+output

for i in range(open):
    if open>0:
        output=output+")"

print(output)

Submission status: Accepted

Solution code:
n = int(input())
a = list(input())
b = []
cou1=0

for i in a:
    if i=="(":
        cou1 += 1
        b.append("(")
    else:
        b.append(")")
        if cou1==0:
            b.insert(0,"(")
            continue
        cou1 -= 1

for _ in range(cou1):
    b.append(")")

print(*b,sep='')

Submission status: Accepted

Solution code:
N = int(input())
S = input()
left = 0
right = 0
score = 0
for i in range(len(S)):
    if(S[i] is "("):
        if(score < 0):
            left -= score
            score = 1
        else:
            score += 1
    else:
        score -= 1

if(score < 0):
    left -= score
else:
    right += score

for i in range(left):
    S = "(" + S
for i in range(right):
    S = S + ")"
print(S)

Submission status: Accepted

Solution code:
N = input()
string = input()
arrange = string
while True:
    after_arrange = arrange.replace('()','')
    if after_arrange == arrange:
        break
    arrange = after_arrange
left = after_arrange.count(')')
right = after_arrange.count('(')
print('('*left+string+')'*right)

Submission status: Accepted

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

output = ''

hiraki = 0
for i in S:
    if i == '(':
        hiraki += 1
        output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            output = '(' + output
            output += i

output += ')' * hiraki

print(output)

Submission status: Accepted

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

s = ""
left = 0
right = 0

for a in l:
	if a == "(":
		left += 1
	else:
		if left <= right:
			s = "(" + s
			left += 1
		right += 1
	s += a

if left - right < 0:
	for x in range(right - left):
		s = "(" + s
else:
	for x in range(left - right):
		s += ")"

print (s)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Out =  S[:]
while len(S) > 0:
	if S[0] == ")":
		Out.insert(0,"(")
		del S[0]
	elif S[0] == "(":
		for j in range(len(S)):
			if S[j] == ")":
				del S[j]
				del S[0]
				break
			elif j == len(S) - 1 :
				Out.append(")")
				del S[0]
print(''.join(Out))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Out =  S[:]
while len(S) > 0:
	if S[0] == ")":
		Out.insert(0,"(")
		del S[0]
	elif S[0] == "(":
		i = 0
		for j in range(len(S)):
			if S[j] == ")":
				del S[j]
				del S[0]
				i += 1
				break
			elif j == len(S) - 1 :
				Out.append(")")
				del S[0]
print(''.join(Out))

Submission status: Accepted

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

output = ''

hiraki = 0
toji = 0
for i in S:
    if i == '(':
        if toji > 0:
            output = '(' * toji + output
            toji = 0
            hiraki += 1
            output += i
        else:
            hiraki += 1
            output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            toji += 1
            output += i

output += ')' * hiraki
output = '(' * toji + output

print(output)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Out =  S[:]
Temp = S[:]
while len(Temp) > 0:
	if Temp[0] == ")":
		Out.insert(0,"(")
		del Temp[0]
	elif Temp[0] == "(":
		i = 0
		for j in range(len(Temp)):
			if Temp[j] == ")":
				del Temp[j]
				del Temp[0]
				i += 1
				break
		if i == 0:
			Out.append(")")
			del Temp[0]
print(''.join(Out))

Submission status: Accepted

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

output = ''

hiraki = 0
toji = 0
for i in S:
    if i == '(':
        if toji > 0:
            output = '(' * toji + output
            output += ')' * toji
            toji = 0
            hiraki += 1
            output += i
        else:
            hiraki += 1
            output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            toji += 1

for i in range(hiraki):
    output += ')'

for i in range(toji):
    output += ')'

output = '(' * toji + output

print(output)

Submission status: Accepted

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

score = 0
ln = 0
rn = 0

for s in S:
    if s == '(':
        score += 1
    elif s == ')':
        score -= 1

    if score < 0:
        ln += 1
        score = 0

if score > 0:
    rn = score
    score = 0

S = '('*ln + S + ')'*rn
print(S)

Submission status: Accepted

Solution code:
input()
s = input().strip()
stock, depth = 0, 0
for c in s:
    if c == '(':
        depth += 1
    else:
        if depth:
            depth -= 1
        else:
            stock += 1
print('(' * stock + s + ')' * depth)

Submission status: Accepted

Solution code:
input()
s = input().strip()
ans = s
depth = 0
for c in s:
    if c == '(':
        depth += 1
    else:
        if depth:
            depth -= 1
        else:
            ans = '(' + ans
ans += ')' * depth
print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
s = raw_input()
ct = 0
mn = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
    mn = min(mn,ct)
l = abs(mn)
r = ct + l
s = '('*l + s + ')'*r
print s

Submission status: Accepted

Solution code:
n = int(raw_input())
s = raw_input()
ct = 0
mn = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
    mn = min(mn,ct)
s = '('*abs(mn) + s
ct = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
s = s + ')'*ct
print s

Submission status: Accepted

Solution code:
N=int(input())
r=0
l=0
S = input()
li_S = []
count = 0

for i in range(N):
    if S[i]==")":
         r += 1
         li_S.append(")")
    else:
        l += 1
        li_S.append("(")
    if r > l :
        li_S.insert(0,"(")
        l += 1

for i in range(l-r):
    li_S.append(")")
print("".join(li_S))

Submission status: Accepted

Solution code:
N = input()
S = raw_input()
ans = ""
cnt = 0
for ch in S:
    if (cnt <= 0) and (ch == ")"):
        ans = "(" + ans
    elif (ch == ")"):
        cnt -= 1
    else:
        cnt += 1
    ans += ch
ans += ")" * cnt
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys, re

N = input()
S = input()
sentence = ''
left, right = 0, 0
for s in S:
    sentence += s
    if s == '(':
        left += 1
    else:
        right += 1
    if left - right < 0:
        sentence = '(' + sentence
        left += 1
if left - right > 0:
    sentence = sentence + ')' * (left - right)
print(sentence)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys, re

N = input()
S = input()
# pattern = re.compile(r'\)\(')
sentence = ''
left, right = 0, 0
# lit = []
for s in S:
    sentence += s
    if s == '(':
        left += 1
    else:
        right += 1
    if left - right < 0:
        sentence = '(' + sentence
        left += 1
if left - right > 0:
    sentence = sentence + ')' * (left - right)
print(sentence)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
head = ""
depth = 0
for i in s:
    if i == "(":
        depth += 1
    else:
        if depth == 0:
            head += "("
        else:
            depth -= 1
tail = ")" * depth
print(head + s + tail)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
head = ""
depth = 0
for i in s:
    if i == "(":
        depth += 1
    else:
        if depth == 0:
            head += "("
        else:
            depth -= 1
tail = "".join([")" for _ in range(depth)])
print(head + s + tail)

Submission status: Accepted

Solution code:
input()
s = input()
stk = list()
for c in s:
    if c == '(':
        stk.append('(')
    elif len(stk) != 0 and stk[-1] == '(':
        stk.pop()
    else:
        stk.append(')')
print(stk.count(')') * '(' + s + stk.count('(') * ')')

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open("d1.in")

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

c = 0
m = 0
M = 0

for l in s:
    if l == '(':
        c += 1
    if l == ')':
        c -= 1
    if m > c:
        m = c
    if M < c:
        M = c

left = '(' * (-m)
c += -m
right = ')' * c
res = left + s + right
print(res)

Submission status: Accepted

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

cnt = 0

ans = []

for s in S:
    if s =="(":
        if cnt >= 0:
            cnt += 1
            ans.append(s)
        else:
            ans.append(s)
            cnt = 0 - cnt
            for _ in range(cnt):
                ans.insert(0, s)
            cnt = 1
    else:
        if cnt <= 0:
            cnt -= 1
            ans.append(s)
        else:
            ans.append(s)
            cnt -= 1

if cnt > 0:
    for _ in range(cnt):
        ans.append(")")
elif cnt < 0:
    cnt = 0 - cnt
    for _ in range(cnt):
        ans.insert(0, "(")

print(''.join(ans))

Submission status: Accepted

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

cur = 0
pre = 0
for c in s:
    if c == '(':
        cur += 1
    else:
        cur -= 1

    if cur < 0:
        pre += 1
        cur += 1

print("("*pre + s + ")"*cur)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
start = 0
end = 0

for i in range(n):
    if s[i] == "(":
        start += 1
    elif s[i] == ")" and start <= 0:
        end += 1
    else:
        start -= 1

print("("*end+s+")"*start)

Submission status: Accepted

Solution code:
import copy

n = int(input())
s = input()
deeps = copy.deepcopy(s)

while s.count("()") >= 1:
    s = s.replace("()","")

ans = s.count(')')* '(' + deeps + s.count('(')*')'

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
begin = 0
end = 0
for i in range(N):
    if(S[i] == "(" ):
        begin += 1
    elif(S[i] == ")" and begin <= 0):
        end += 1
    else:
        begin -= 1
S = ("(" * end) + S + (")" * begin)
print(S)

Submission status: Accepted

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

# Initialize
N = int(input())
S = list(input())

def output(start, end):
    ans = ""
    for i in range(start):
        ans += "("
    for i in S:
        ans += i
    for i in range(end):
        ans += ")"
    return ans

stock = 0
lack_start = 0
lack_end = 0

for s in S:
    if s == '(':
        stock += 1
    elif s == ')':
        if stock > 0:
            stock -= 1
        else:
            lack_start += 1

lack_end = stock
print(output(lack_start, lack_end))

Submission status: Accepted

Solution code:
#coding:utf-8

if __name__ == "__main__":
    N = int(input())
    string = input()

    right = 0
    left = 0

    for char in string:
        if char == '(':
            right += 1
        else:
            right -= 1

        if right == -1:
            left += 1
            right = 0

    L = '(' * left
    R = ')' * right

    print(L + string + R)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    s = S()
    d = collections.defaultdict(int)
    for c in s:
        d[c] += 1
    l = d['(']
    r = d[')']

    if l > r:
        s += ')' * (l-r)
    elif r > l:
        s = '(' * (r-l) + s

    c = 0
    rc = 0
    i = 0
    while i < len(s):
        if s[i] == '(':
            c += 1
        else:
            c -= 1
        if c < 0:
            rc += 1
            c = 0
        i += 1
    s = '(' * rc + s + ')' * rc
    return s


print(main())

Submission status: Accepted

Solution code:
n = int(input())
s = input()
bf = []
af = []
st = ['*']

for c in s:
    pre = st[-1]
    st.append(c)    

    if c ==  ')':
        if (pre == '(') :
            st.pop()
            st.pop()
            af.pop()
            continue
        bf.append('(')
    else:
        af.append(')')
ans = ''.join(bf) + s + ''.join(af)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin 
n = int(stdin.readline())
a = stdin.readline().strip()
x = 0
fir = 0 
sec = 0
for i in a:
    if i=='(':
        fir+=1
    else:
        if fir > 0:
            fir-=1
        else:
            sec+=1
            fir = 0

print sec*'(' + a + ')'*fir

Submission status: Accepted

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

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

    if acc == -1:
        l += 1
        acc += 1

L = '(' * l
R = ')' * acc
print (L + S + R)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
stack_num = 0
ind = 0
ret = ""
nr = 0
for c in s:
    if(c == "("):
        stack_num += 1
    else:
        stack_num -= 1
    if(stack_num < 0):
        ret += "("
        stack_num += 1
if(stack_num < 0):
    ret += "(" * (-stack_num)
ret += s
if(stack_num >= 0):
    ret += ")" * stack_num
print(ret)

Submission status: Accepted

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

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

    if len(s) == 0:
        print(S)
        return

    left = ''
    right = ''
    if s[0] == ')':
        left = '(' * s.count(')')
    if s[-1] == '(':
        right = ')' * s.count('(')

    print('{}{}{}'.format(left, S, right))

main()

Submission status: Accepted

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

    s = S
    while True:
        s = s.replace('()', '')
        if s.count('()') == 0:
            break

    if len(s) == 0:
        print(S)
        return

    left = ''
    right = ''
    if s[0] == ')':
        left = '(' * s.count(')')
    if s[-1] == '(':
        right = ')' * s.count('(')

    print('{}{}{}'.format(left, S, right))

main()

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()


n = ni()
s = ns()

level = 0
left = 0

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

print('(' * left + s[0:n] + ')' * level)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
s = S[:]
while '()' in s:
	s = s.replace('()','')

print('('*s.count(')') + S + ')'*s.count('('))

Submission status: Accepted

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

v = []
tmp =[]

for s in S:
    if s == "(":
        tmp.append(")")
        v.append("(")
    else:
        if len(tmp) == 0:
            v.insert(0, "(")
            v.append(")")
        else:
            v.append(tmp.pop())

while tmp:
    v.append(tmp.pop())

print("".join(v))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
time = int(input())
kakko = input()
hidarikakko = 0 #(
migikakko = 0 #)
hidariHuyasu = 0 #左に増やす(の数
migiHuyasu = 0 #右に
#左に増やすのを考える
for i in range(time):
    if kakko[i] == "(":
        hidarikakko += 1
    else:
        if hidarikakko == 0:
            hidariHuyasu += 1
        else:
            hidarikakko -= 1
#右に増やすのを考える
hidarikakko = 0 #(
migikakko = 0 #)
gyaku = range(time)
# print(gyaku)
# gyaku.reverse()
for i in reversed(range(time)):
    if kakko[i] == ")":
        migikakko += 1
    else:
        if migikakko == 0:
            migiHuyasu += 1
        else:
            migikakko -= 1
print("(" * hidariHuyasu + kakko + ")" * migiHuyasu)

Submission status: Accepted

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


v = []


stock = 0

for i in s:
    if i=="(":
        stock+=1
        v.append("(")
    else:
        if stock ==0:
            v.insert(0,"(")
            v.append(")")
        else:
            stock -= 1
            v.append(")")

for i in range(stock):
    v.append(")")

print(*v,sep='')

Submission status: Accepted

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

str1=str
str2=str
n=int(N/2)

for var in range(1,n+1):
    try:
        str1=str1.replace("()","")
    except:
        break

s1=str1.count("(")
s2=str1.count(")")

print("("*s2+str2+")"*s1)

Submission status: Accepted

Solution code:
input()
S = input()
c = 0
m = 0
for s in S:
 if s == "(":
  c += 1
 else:
  c -= 1
 if c < 0:
  m += 1
  c += 1
print("("*m+S+")"*c)

Submission status: Accepted

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

y=[0]*N
left=''
right=''

for i in range(N):
    if (x[i]==')'):
        y[i]=-1
    else:
        y[i]= 1

for i in range(N):
    if y[i]==1:
        for j in range(i,N):
            if y[j]==-1:
                y[i]=y[j]=0
                break



for i in range(y.count(-1)):
    left=left+'('
for i in range(y.count(1)):
    right=right+')'

print(left+x+right)
        
quit()

Submission status: Accepted

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

stack=[]
stack2=[]
index=-1
index2=-1


#append ")" at the end of S
for i in range(N):
    stack.append(S[i])
    index+=1

    if len(stack)==1 and stack[0]==')':
        del stack[0]
        index-=1

    elif stack[index-1]=='(' and stack[index]==')':
        stack.pop(index)
        stack.pop(index-1)
        index-=2
    #print(stack)

last=len(stack)
for i in range(last):
    S=S+")"

#print("S"+S)

T=S[::-1]


#print("T"+T)

leng=len(T)
for i in range(leng):
    stack2.append(T[i])
    index2+=1

    if len(stack2)==1 and stack2[0]=='(':
        del stack2[0]
        index2-=1

    elif stack2[index2-1]==')' and stack2[index2]=='(':
        stack2.pop(index2)
        stack2.pop(index2-1)
        index2-=2
    #print(stack2)

first=len(stack2)
for i in range(first):
    T=T+"("

#print(T)
print(T[::-1])

Submission status: Accepted

Solution code:
N = input()
string = [x for x in input()]
strings = string[:]  # manipulate
stack = []

for i in range(len(strings)):
    if strings[i] == '(':
        stack.append(1)
    elif strings[i] == ')':
        if not stack:
            string.insert(0,'(')
        else:
            stack.pop()

if stack:
    for i in range(len(stack)):
        string.append(')')

print(''.join(string))

Submission status: Accepted

Solution code:
input();s=input();l=0
exec("r=l\nfor c in'%s':l=max(l-1+2*(c=='%s'),0)\n"*2%(s,'(',s[::-1],')'))
print(l*'('+s+')'*r)

Submission status: Accepted

Solution code:
a = int(input())
c = input()
nl = 0
nr = 0
for i in c :
    if i == ')' :
        nr += 1
        if nl > 0 :
            nr -= 1
            nl -= 1
    elif i == '(' :
        nl += 1
c = '('*nr + c + ')'*nl
print(c)

Submission status: Accepted

Solution code:
import sys

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

tries = []

def count(S):
    cnt = 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
    return cnt

def valid(S):
    cnt = 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return False
    return True

def bt(S):
    cnt = count(S)
    if count(S) == 0 and valid(S):
        tries.append(S)
        return
    else:
        if cnt < 0:
            return bt("(" + S)
        else:
            return bt(S + ")")
bt(s)
print(min(tries))

Submission status: Accepted

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

l=0
R=0
for sbk in bk:
    if sbk==')':
        if l==0:
            R+=1
        else:
            l-=1
    else:
        l+=1



r=0
L=0
for sbk in reversed(bk):
    if sbk=='(':
        if r==0:
            L+=1
        else:
            r-=1

    else:
        r+=1




res='('*R+"".join(bk)+')'*L
print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
copy = s
s_list = list(s)
left_list = []
right_list = []

n = len(s_list)
flag = 1
if len(s_list) > 1:
    while flag == 1:
        flag = 0

        if n>=1:
            for i in range(n-1):
                if s_list[i] == '(' and s_list[i+1] == ')':
                    s_list.pop(i)
                    s_list.pop(i)
                    n -= 2
                    flag = 1
                    break

        else:
            break




for word in s_list:
    if word == ')':
        left_list.insert(0,'(')
    else:
        right_list.insert(len(right_list),')')


word = ""

for lef in left_list:
    word += lef

word += s

for rig in right_list:
    word += rig

print(word)

Submission status: Accepted

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

right = 0
left = 0
sum_right = 0
sum_left = 0

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

print(s)

Submission status: Accepted

Solution code:
input();s=input();r=l=0
for c in s:r=max(r-1+2*(c=='('),0)
for c in s[::-1]:l=max(l-1+2*(c==')'),0)
print(l*'('+s+')'*r)

Submission status: Accepted

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

def step(queue_l, queue_r, c):
    if c == '(':
        queue_l += 1
    else:
        if queue_l > 0:
            queue_l -= 1
        else:
            queue_r += 1
    return (queue_l, queue_r)


out = []
queue_l = 0
queue_r = 0
for c in S:
    queue_l, queue_r = step(queue_l, queue_r, c)

print('(' * queue_r + S + ')' * queue_l)

Submission status: Accepted

Solution code:
import numpy as np
# import random
def d2():
    n = int(input())
    s = input()
    l = [ 1 if x=='(' else -1 for x in s[:] ]
    mt = np.cumsum(l) # mountain
    mi = min(0, np.amin(mt))
    left = ''; right = ''
    if mi < 0:
        left = '('*(mi*-1)
    if mt[-1]-mi > 0:
        right = ')'*(mt[-1]-mi)
    # print(mt, mi)
    print(left + s + right)

d2()

Submission status: Accepted

Solution code:
N = int(input())
data = list(input())
app = [0,0]
for i in range(N):
    if data[i] == ")":
        app[0] += 1
        if app[1] > 0:
            app[0] -= 1
            app[1] -= 1
    elif data[i] == "(":
        app[1] += 1
print("("*app[0] + "".join(data) + ")"*app[1])

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    input_raw = list((read_func().strip()))
    S = list(input_raw)
    left_count = 0
    for i in range(N):
        if input_raw[i] == '(':
            left_count += 1

        if input_raw[i] == ')':
            if left_count > 0:
                left_count -= 1
            else:
                S.insert(0, '(')

    for i in range(left_count):
        S.append(')')
    print "".join(S)



if __name__ == '__main__':
    main()