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())
data=list(map(lambda x:[str(x),-1],input()))
while 1:
    i=0
    while i<len(data):
        if data[i][0]==')' and data[i][1] == -1:
            break
        i+=1
    if i==len(data):
        break
    j=i-1
    while j>=0:
        if data[j][0]=='(' and data[j][1]==-1:
            data[i][1]=1
            data[j][1]=1
            break
        j-=1
    if j==-1:
        data[i][1]=1
        data.insert(0,['(',1])
while 1:
    i=len(data)-1
    while i>=0:
        if data[i][0]=='(' and data[i][1] == -1:
            break
        i-=1
    if i==-1:
        break
    data[i][1]=1
    data.append([')',1])
print(''.join(list(map(lambda x:x[0],data))))

Submission status: Accepted

Solution code:
N = int(raw_input())
S = raw_input()
S_sub = S
while ("()" in S):
    S = S.replace("()","")
a = 0
b = 0
for x in S:
    if x == ')':
        a += 1
    else:
        break
for x in S:
    if x == '(':
        b += 1
print "(" * a + S_sub + ")" * b

Submission status: Accepted

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

s=list(S)

i=0
j=0
while i<N and j<N:
    #print i,s
    if s[i]=='(':
        j=i
        while j<N:
            #print i,j
            if s[j]==')':
                s[i]='x'
                s[j]='x'
                #print (i,j),s
                i+=1
                break
            else:
                j+=1
    else:
        i+=1

op=s.count(')')
cl=s.count('(')

print '('*op+S+')'*cl

Submission status: Accepted

Solution code:

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

l = []
l.append(S)
i = 0
while True:
    if i > 1 and l[i] == l[i-1]:
        break
    l.append(l[i].replace("()",""))
    i += 1

a = l[i]
left = a.count(')')
right = a.count('(')
ans = '('*left + S + ')'*right
print(ans)

Submission status: Accepted

Solution code:
class Parenter:
    def __init__(self):
        self.left = 0
        self.right = 0
        self.data = ""

    def _run(self, letter):
        if letter == "(":
            self.data += "("
            self.left += 1
        if letter == ")":
            if self.left > 0:
                self.left -= 1
                self.data += ")"
            else:
                self.right += 1
                self.data += ")"
    
    def run(self, string):
        for s in string:
            self._run(s)
        self.data = "("*self.right + self.data + ")"*self.left
    

p = Parenter()
N = input()
data = input()
p.run(data)
print(p.data)

Submission status: Accepted

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

def insert(string):
    # str_len = len(string)
    # print str_len
    left = 0
    right = 0
    i=0
    while i < len(string):
        if string[i] == "(":
            left += 1
            # print "left is " + str(left)
        else:
            right += 1
            # print "right is " + str(right)
        if right > left:
            string = "(" + string
            left += 1
            # print string
            i=0
            left = 0
            right = 0
        else:
            i += 1
    return string

def add_ket(string):
    bra = 0
    ket = 0
    for i in range(len(string)):
        if string[i] == "(":
            bra += 1
        else:
            ket += 1
    add = bra-ket
    string = string + add * ")"
    return string


tmp = insert(S)
print add_ket(tmp)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
S = list(input())
S_v = np.array(S)
def pop(S):
    index=[]
    for i in range(len(S)-1):
        if S[i]=='('and S[i+1]==')':
            index.append(i)
            index.append(i+1)
    index = np.array(index)
    answer = np.delete(S,index)
    return answer
p = np.array([])
while len(S_v)!=len(p):
    p = S_v
    S_v = pop(S_v)
#print (S_v)
n_left = len(np.where(S_v==')')[0])
n_right = len(np.where(S_v=='(')[0])
print ('('*n_left+''.join(S)+')'*n_right)

Submission status: Accepted

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

opened = 0
min_opened = 0
for c in S:
    if c == '(' :
        opened += 1
    else:
        opened -= 1
        min_opened = min(opened, min_opened)

closed = 0
min_closed = 0
for c in S[::-1]:
    if c == ')' :
        closed += 1
    else:
        closed -= 1
        min_closed = min(closed, min_closed)

op = '(' * -min_opened if min_opened < 0 else ''
cl = ')' * -min_closed if min_closed < 0 else ''
print op + S + cl

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    S = input()
    tmpS = S
    for i in range(50):
        tmpS = tmpS.replace("()", "")

    # print(tmpS)
    left_parenthesis_count = 0
    right_parenthesis_count = 0
    for moji in tmpS:
        if moji == "(":
            left_parenthesis_count += 1
        elif moji == ")":
            right_parenthesis_count += 1

    ans = S
    for i in range(right_parenthesis_count):
        ans = "(" + ans

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

    print(ans)

Submission status: Accepted

Solution code:
import copy

if __name__ == "__main__":

    N = int(input())
    s = input().replace("\n","")

    left = 0
    cp_s = copy.copy(s)
    for c in s:
        if c == "(":
            left += 1
        else:
            left -= 1
        if left < 0:
            cp_s = "(" + cp_s
            left += 1
    if left > 0:
        cp_s = cp_s + ")"*left
    print(cp_s)

Submission status: Accepted

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

def ans(S, cnt=0):
    H = []
    for i in S:
        if i == ")":
            if H:
                H.pop()
            else:
               cnt += 1
        else:
            H.append(1)
    return [cnt, len(H)]

L = ans(S)
A = "(" * L[0]
Z = ")" * L[1]

print(A + S + Z)

Submission status: Accepted

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

n = input()
s = raw_input()
cnt = 0
flg = 1
while(flg):
    for i in range(len(s)):
        if(s[i] == '('):
            cnt += 1
        elif(s[i] == ')'):
            cnt -= 1
            if(cnt<0):
                s = '('+s
                cnt = 0
                break
        if(i==len(s)-1):
            flg = 0
for i in range(cnt):
    s = s+')'
print(s)

Submission status: Accepted

Solution code:
import re

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

while True:
    pre = S
    S = re.sub(r'\(((L|R)*?)\)', r'L\1R', S)
    if pre == S:
        break

S = '(' * S.count(')') + S + ')' * S.count('(')
S = S.replace('L', '(')
S = S.replace('R', ')')
print(S)

Submission status: Accepted

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

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

result = '(' * leftAdd + S + ')' * leftCount
print(result)

Submission status: Accepted

Solution code:
N = int(input())

parentheses = list(input())

add_open = 0
close_buff = 0

result = ""

for elem in parentheses:
    result += elem

    if elem == "(":
        close_buff += 1

    elif elem == ")":
        if close_buff > 0:
            close_buff -= 1
        else:
            add_open += 1

print("("*add_open + result + ")"*close_buff)

Submission status: Accepted

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

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

left_count = s.count(")")
right_count = s.count("(")

for i in range(left_count):
    s_original = "(" + s_original
    
for i in range(right_count):
    s_original = s_original + ")"
    
print(s_original)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
ans = []
st = 0
for c in S:
    if c == '(':
        st += 1
        ans.append('(')
    else:
        if st > 0:
            st -= 1
        else:
            ans.insert(0, '(')
        ans.append(')')
 
ans.extend(')' * st)
 
print(*ans, sep='')

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
stack = []
l = 0
for i,c in enumerate(S):
  if c == ')':
    if stack:
      stack.pop()
    else:
      l += 1
  else:
    stack.append(i)
ans = '('*l + S + ')'*len(stack)
print(ans)

Submission status: Accepted

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

t = S

while S.count("()") != 0:
    S = S.replace("()", "")

L = S.count("(")
R = S.count(")")

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def is_correct(s):
    l = 0
    for si in s:
        if si == "(": l += 1
        else: l -= 1
        if l < 0: return False
    return l == 0

N = int(raw_input())
S = raw_input()

flag = False
for i in xrange(105):
    for j in xrange(105):
        T = "("*i + S + ")"*j
        if is_correct(T):
            print T
            flag = True
            break
    if flag:
        break

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
stack = []


for v in s:
    if stack and stack[-1] == "(" and v == ")":
        stack.pop()
    else:
        stack.append(v)


for v in stack:
    if v == ")":
        s.insert(0, "(")
    else:
        s.append(")")

print("".join(s))

Submission status: Accepted

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

from copy import deepcopy
N = int(input())
S = input()
rawS = deepcopy(S)

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

right = S.count("(")
left = S.count(")")
print("("*left + rawS + ")"*right)

Submission status: Accepted

Solution code:
import sys

def main():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().rstrip()

    level = 0 #level個の(括弧が開いている
    left_paren_app_num = 0
    right_paren_app_num = 0

    #イキナリ)括弧が出てくるか、
    #(括弧で終わっているとマズい

    for ch in s:
        if ch == '(':
            if level < 0:
                left_paren_app_num += - level
                level = 0
            level += 1
        elif ch == ')':
            level -= 1

    if level > 0:
            right_paren_app_num += level
            level = 0
    elif level < 0:
        left_paren_app_num += - level


    l_s = "".join(['(' for i in range(left_paren_app_num)])
    r_s = "".join([')' for i in range(right_paren_app_num)])
    print("%s%s%s" % (l_s, s, r_s))
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

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

v1 = 0
v = 0
for s in S:
    if s == "(":
        v -= 1
    if s == ")":
        v += 1
    v1 = max(v1, v)

v2 = v1 + S.count("(") - S.count(")")

print "(" * v1 + S + ")" * v2

Submission status: Accepted

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

def get_purified(string):
    replaced = string.replace("()", "")
    if replaced == string:
        return replaced
    else:
        return get_purified(replaced)

purified_str = get_purified(S)
right_braces = purified_str.count("(")
left_braces = purified_str.count(")")
out = "(" * left_braces + S + ")" * right_braces
print(out)

Submission status: Accepted

Solution code:
n=int(raw_input())
s=raw_input()
cnt1=0
cnt2=0
for i in xrange(n):
    if s[i]=="(":
        cnt1+=1
    else:
        if cnt1>0:
            cnt1-=1
        else:
            cnt2+=1

for i in xrange(cnt1):
    s+=")"
for i in xrange(cnt2):
    s="("+s
print s

Submission status: Accepted

Solution code:
def makeinsert(s):
	left = 0
	inserttop = ''
	for i in range(0, len(s)):
		if s[i] == '(':
			left += 1
		else:
			if left > 0:
				left -= 1
			else:
				inserttop = '(' + inserttop
	insertbottom = ''
	for i in range(0, left):
		insertbottom = insertbottom + ')'
	return inserttop + s + insertbottom

raw_input()
s = raw_input()

print makeinsert(s)

Submission status: Accepted

Solution code:
#!/usr/local/bin/python3.5 -tt

import random
import sys

if __name__ == '__main__':
    def _(f):
        for l in f:
            for i in l.split():
                yield i

    g = _(sys.stdin)

    N, S = (int(next(g)),
                next(g),
    )

    SS = S

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

        while S.startswith(')'):
            S = S[1:]
            
            SS = '(' + SS

        while S.endswith('('):
            S = S[:-1]

            SS += ')'

    print(SS)

Submission status: Accepted

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

n = int(input())
s = input()
t0 = 0
t1 = 0
ans = s
for i in s:
    if i == '(' : t0 += 1
    if i == ')' : t1 += 1
    if t0 < 1 and t1 > 0:
        t1 -= 1
        ans = '(' + ans
    if t0 > 0 and t1 > 0:
        t0 -= 1
        t1 -= 1
print(ans + ')' * t0)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
	N = int(input())
	S = input()
	left = []
	right = []
	for i,p in enumerate(S):
		if p == '(':
			left.append(i)
		else:
			if (len(left) > 0):
				left.pop(0)
			else:
				right.append(i)
	for x in range(len(right)):
		S = '(' + S
	for x in range(len(left)):
		S = S + ')'
	print (S)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
r = 0
l = 0
for s in S:
	if s == "(":
		l += 1
	else:
		if l == 0:
			r += 1
		else:
			l -= 1
r2 = 0
l2 = 0
for s in S[::-1]:
	if s == ")":
		r2 += 1
	else:
		if r2 == 0:
			l2 += 1
		else:
			r2 -= 1
S = ["("] * r + S + [")"] * l
print("".join(S))

Submission status: Accepted

Solution code:


def main():
    n = int(raw_input())
    s = raw_input()

    total = 0
    prep = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1

        if total < 0:
            prep += 1
            total = 0

    print '(' * prep + s + ')' * total


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(raw_input())
s=raw_input()
stack=[]
stidx=[]
ins=[]
for i in xrange(n):
    if s[i]=="(":
        stack.append(s[i])
        stidx.append(i)
    else:
        if len(stack)==0:
            ins.append(i)
        else:
            stack.pop()
            stidx.pop()
tmp=list(s)
for i in stidx:
    tmp[n-1]=tmp[n-1]+")"
for i in xrange(len(ins)):
    tmp[0]="("+tmp[0]
print "".join(tmp)

Submission status: Accepted

Solution code:
N=int(input())
S=str(input())
s=S[:]
while "()" in s:
  s=s.replace("()","")
st=s.count(")")
gl=s.count("(")
print("("*st+S+")"*gl)

Submission status: Accepted

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

import sys
import os

N = int(input())
s = input().strip()
t = s

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

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

answer = '(' * right + s + ')' * left

print(answer)

Submission status: Accepted

Solution code:
n = raw_input()
s = raw_input()
stack = []
for l in s:
    stack.append(l)
    if stack[-2:] == ["(", ")"]:
        stack.pop()
        stack.pop()
for l in stack:
    if l == ")":
        s = "(" + s
    if l == "(":
        s += ")"

print s

Submission status: Accepted

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

a=0
b=0
c=0
for c in s:
    if c=='(':
        a+=1
    else:
        if a>0:
            a-=1
        else:
            b+=1

s+=')'*a
s = '('*b+s

print(s)

Submission status: Accepted

Solution code:
# coding: utf-8
def get_ln_inputs():
    return input().split()


def main():
    _ = get_ln_inputs()
    S = get_ln_inputs()[0]

    level = 0
    index = 0
    while index < len(S):
        if S[index] == "(":
            index += 1
            level += 1
            continue
        if S[index] == ")":
            if level > 0:
                index += 1
                level -= 1
                continue
            S = "(" + S
            index += 2
    print(S + (")" * level))


main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a = s
f = 0
for c in a:
	if c=="(":
		f+=1
	else:
		if f>0:
			f-=1
		else:
			s = "(" + s
for i in range(f):
	s = s + ")"

print(s)

Submission status: Accepted

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

def solve(N, S):
    n_close = 0
    max_n_close = 0
    for s in S:
        if s == ')':
            n_close += 1
            max_n_close = max(max_n_close, n_close)
        if s == '(':
            n_close -= 1
    SS = '(' * max_n_close + S
    n_open = SS.count('(')
    n_close = SS.count(')')
    SSS = SS + ')' * (n_open - n_close)
    return SSS

print(solve(N, S))

Submission status: Accepted

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

l = ""
r = ""
cnt = 0
for i in S :
	if i == '(' :
		cnt += 1
	else :
		cnt -= 1
	
	if cnt < 0 :
		cnt += 1
		l += '('

r = ')' * cnt

print(l + S + r)

Submission status: Accepted

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

Submission status: Accepted

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

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

_ = input()
S = input()
stack = 0
made = ''
for ch in S:
    # print("ch, stack = ", ch, stack)
    if ch == '(':
        stack += 1
        made += '('
    elif ch == ')':
        if stack == 0:
            made = '(' + made + ')'
        else:
            made += ')'
            stack -= 1
made += ')' * stack
print(made)

Submission status: Accepted

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

pre=""
cnt=0
for s in S:
    if s == "(":
        cnt += 1
    else:
        if cnt == 0:
            pre += "("
        else:
            cnt -= 1

suf=")"*cnt

print pre+S+suf

Submission status: Accepted

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

input()
s = input()
balance = 0
left = 0
for c in s:
    if c == '(':
        balance += 1
    elif balance == 0:
        left += 1
    else:
        balance -= 1
right = balance
print('(' * left + s + ')' * right)

Submission status: Accepted

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

op,cl=0,0
for c in s:
    if c=='(':
        op+=1
    else:
        if op>0:
            op-=1
        else:
            cl+=1
print(('('*cl)+s+(')'*op))

Submission status: Accepted

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

l, r = 0, 0
tmp = 0
for i in xrange(N):
    if S[i] == '(':
        tmp += 1
    else:
        tmp -= 1
        if tmp < 0:
            l += 1
            tmp = 0

tmp = 0
for i in xrange(N-1, -1, -1):
    if S[i] == ')':
        tmp += 1
    else:
        tmp -= 1
        if tmp < 0:
            r += 1
            tmp = 0
print '(' * l + S + ')' * r

Submission status: Accepted

Solution code:
import sys
n = map(int, sys.stdin.readline().split())
a = sys.stdin.readline().strip()
res = a
h = 0
for i in range (len(a)):
  if a[i] == '(':
    h += 1
  else:
    h -= 1
  if h < 0:
    res = '(' + res
    h = 0

print res + ')' * h

Submission status: Accepted

Solution code:
n = input()
s = raw_input()
right = 0
for i in xrange(n):
    if s[i] == '(':
        right += 1
    else:
        right = max(right-1, 0)
left = 0
for i in xrange(n-1, -1, -1):
    if s[i] == ')':
        left += 1
    else:
        left = max(left-1, 0)
print '('*left+s+')'*right

Submission status: Accepted

Solution code:
n = int(raw_input())
s = raw_input()
m = 0
c = 0
for si in s:
    if si == "(":
        c += 1
    else:
        c -= 1
    m = min(m, c)

ans = ""
if m < 0:
    ans += "(" * (-m)
    c += -m

if c < 0:
    ans = ans + "(" * (-c) + s
else:
    ans = ans + s + ")" * c

print ans

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().strip()
h = 0
minh = 0
for c in s:
    if c == "(":
        h += 1
    else:
        h -= 1
    minh = min(minh, h)
print("("*(-minh) + s + ")"*(h-minh))

Submission status: Runtime Error

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

right = 0
left = 0

divid = [0]
for s_1 in range(len(S)-1):
    s_2 = s_1+1
    if S[s_1] == ')' and S[s_2] == '(':
        divid.append(s_2)
divid.append(len(S))

for s1,s2 in zip(divid[:-1],divid[1:]):
    S_temp = S[s1:s2]
    right_temp = 0
    left_temp = 0
    for s in S_temp:
        if s == '(':
            left_temp += 1
        if s == ')':
            right_temp += 1    
    
    right += max(0,right_temp - left_temp)
    left += max(0,left_temp - right_temp)
    
#     print(s1,s2,S_temp)
#     print(right,left)
print('('*right+S_+')'*left)

Submission status: Runtime Error

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

ans = ""
index = 0


left = 0
right = 0


for i in range(n):
    if s[-i-1] == ")":
        index1 = n - i 
        break
for i in range(n):
    if s[i] == "(":
        index2 = i
        break

#s = "(" * index2 + s

lis = s[index2:index1]
left = lis.count("(") 
right = lis.count(")") 
if right >= left:
    ans +="(" * index2 + "(" * (right-left) + s + ")" * (n-index1)
else:
    ans +="(" * index2 + s + ")" * (left-right) + ")"  * (n-index1)


print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(N):
    if s[i] == '(':
        ind1 = i
        break

for i in range(N):
    if s[N-i-1] == ')':
        ind2 = N-i
        break

left = s[:ind1].count(')')
right = s[ind2:].count('(')

mid_left = s[ind1:ind2].count(')')
mid_right = s[ind1:ind2].count('(')

left += max(0,mid_left-mid_right)
right += max(0,mid_right-mid_left)

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
def main():
    n = int(input())
    s = input()
    t = s.split(')(')
    if len(t) == 1:
        u = t[0].split('()')
        print(u)
        v = max(len(u[0]), len(u[1])) + 1
        ans = v * '(' + v * ')'
        print(ans)
        exit()

    ans = ''
    for x in t:
        l = len(x) + 1
        ans += l * '(' + l * ')'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
s = input()
ans = s
while True:
    visited = [0]*(len(s))
    t = ""
    for i in range(len(s)-1):
        if not visited[i]:
            if s[i:i+2] == "()":
                visited[i+1] = 1
            else:
                t += s[i]
    if not visited[len(s)-1]:
        t += s[-1]
    s = t
    if not s:
        print(ans)
        sys.exit()
    if not "(" in s or not ")" in s:
        break
    for i in range(s.index(")(")+1,len(s)):
        if s[i] != "(":
            break
    else:
        break
print("("*s.count(")")+ans+")"*s.count("("))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
ans = s
while True:
    visited = [0]*(len(s))
    t = ""
    for i in range(len(s)-1):
        if not visited[i]:
            if s[i:i+2] == "()":
                visited[i+1] = 1
            else:
                t += s[i]
    if not visited[len(s)-1]:
        t += s[-1]
    s = t
    if not "(" in s or not ")" in s:
        break
    for i in range(s.index(")(")+1,len(s)):
        if s[i] != "(":
            break
    else:
        break
print("("*s.count(")")+ans+")"*s.count("("))

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    N=II()
    S=input()
    p = 0
    num_right_p = 0
    ans = ''
    r = 0
    for s in S:
        if s == '(':
            p += 1
        else:
            if p > 0:
                p -= 1
            else:
                r += 1

    
        ans = '(' * r + S + ')' * p
    print(ans)
            
    

    
main()

Submission status: Runtime Error

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    if '(' in S:
        idx = S.index('(')
        cnt = 1
        for s in S[idx+1:]:
            if s == '(':
                cnt += 1
            else:
                cnt -= 1
        res += ')' * max(cnt, 0)
    
    S = S[::-1]
    idx = S.index(')')
    cnt = 1
    for s in S[idx+1:]:
        if s == ')':
            cnt += 1
        else:
            cnt -= 1
    res = '(' * max(cnt, 0) + res

    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    s = list(input())
    left = 0
    right = 0
    for i in range(n):
        if s[i] == '(':
            right += 1
        else:
            if right == 0:
                left += 1
            else:
                right -= 1
    res = ''
    print('('*left+s+')'*right)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
    s = input()
    d = 0
    x = n
    for si in s:
        if si == "(":
            d += 1
        else:
            d -= 1
        x = min(d, x)
    print("(" * -x + s + ")" * (d - x))

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
leng = []
cnt = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        leng.append([s[i], cnt])
        cnt = 1
if s[-1] == "(":
    leng.append(["(", cnt])
else:
    leng.append([")", cnt])
if s[0] == ")":
    leng.insert(0,["(", leng[0][1]])
if s[-1] == "(":
    leng.insert(len(leng),[")", leng[-1][1]])

leng2 = []
for i in range(0, len(leng), 2):
    l = leng[i]
    r = leng[i+1]
    if l[1] == r[1]:
        pass
    elif l[1] < r[1]:
        leng2.append([")",r[1]-l[1]])
    else:
        leng2.append(["(", l[1]-r[1]])

lc = 0
rc = 0
while leng2:
    if leng2[0][0] == ")":
        leng[0][1] += leng2[0][1]
        u = leng2.pop(0)
    else:
        break
while leng2:
    if leng2[-1][0] == "(":
        leng[-1][1] += leng2[-1][1]
        u = leng2.pop()
    else:
        break
lc = 0
rc = 0
for i in range(len(leng2)):
    tar = leng2[i]
    if tar[0] == "(":
        lc += tar[1]
    else:
        rc += tar[1]
if lc > rc:
    s[-1][1] += lc-rc
elif lc < rc:
    s[0][1] += rc-lc

ans = []
for i in range(len(leng)):
    tar = leng[i]
    for j in range(tar[1]):
        ans.append(tar[0])
print("".join(ans))

Submission status: Runtime Error

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

ans = []
while S and S[-1] == '(':
    ans.append(')')
    S.pop()
ans = '(' * len(ans) + ''.join(ans)

cnt = 0
for s in S[::-1]:
    if s == ')':
        cnt += 1
    else:
        cnt -= 1

if cnt > 0:
    ans = '(' * cnt + ''.join(S) + ans
if cnt < 0:
    ans = S + ''.join(S) + ')' * cnt + ans

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

s =str(input())


left_save = 0
dept=0

for i in range(len(s)):
    if s[i] ==')':
        if left_save = 0:
            dept +=1
        else:
            left_save-=1
            
    else:
        left_save+=1

ans = '('*dept + s + ')'*left_save

print(ans)

Submission status: Runtime Error

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

ans_s = s
ans_head = 0
ans_tail = 0

def remove(s):
    while True:
        if len(s) <= 0:
            break
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

while len(s) > 0:
    s = remove(s)
    if s[0] == ')':
        ans_head += 1
        s = remove('(' + s)
    else:
        ans_tail += 1
        s = remove(s + ')')
    # print(s)
print('('*ans_head + ans_s + ')' * ans_tail)

Submission status: Runtime Error

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

ans_s = s
ans_head = 0
ans_tail = 0

def remove(s):
    while True:
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

while len(s) > 0:
    s = remove(s)
    if s[0] == ')':
        ans_head += 1
        s = remove('(' + s)
    else:
        ans_tail += 1
        s = remove(s + ')')
    # print(s)
print('('*ans_head + ans_s + ')' * ans_tail)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
if s[0]==')':
    cnt=1
else:
    cnt=0
for i in range(1,n):
    if s[i]==')' and s[i-1]!='(':
        cnt+=1
    if s[i]==')':
        x=i
print('('*cnt+s+')'*(n-x-1))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
lef2 = s.rindex(")")
rit2 = s.index("(")

ans = s
ans += ")"*(n-(lef2+1))
ans = "("*rit2 + ans
lef = ans.count("(")
rit = ans.count(")")
if lef > rit:
	ans += ")"*(lef-rit)
	print (ans)
elif lef == rit:
	print (ans)
else:
	ans = "("*(rit-lef) + ans
	print (ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
m = 0
c1, c2 = 0, 0
for i in range(n):
    if s[i] == ")":
        m += 1
        c2 = c1
    else:
        c1 += 1
j = 0
while True:
    if s[j] == "(":
        break
    j += 1
l = max((m - c2), j)
s1 = ["("] * l
for i in s:
    if i == "(":
        l += 1
    else:
        l -= 1
s2 = [")"] * l
s = s1 + s + s2
print("".join(s))

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
m, l = 0, 0
c1, c2 = 0, 0
for i in range(n):
    if s[i] == ")":
        m += 1
        c3 = c1
    else:
        c1 += 1
    if s[n - i - 1] == "(":
        l += 1
        c4 = c2
    else:
        c2 += 1
s1 = ["("] * (m - c3)
s2 = [")"] * (l - c4)
s = s1 + s + s2
print("".join(s))

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
r = 0
l = 0
i = 0
if s[0] == ")":
  while(s[i] == ")"):
    l += 1
    i += 1
if s.count("(") > s.count(")")-l:
  r += s.count("(")-(s.count(")")-l)
elif s.count("(") == s.count(")")-l:
  pass
else:
  l += s.count(")")-l-s.count("(")
print(l*"("+"".join(s)+r*")")