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()
copy = s
s_list = list(s)
left_list = []
right_list = []
flag = 0
while True:
    if len(s_list)>1:
        for i in range(len(s_list)-1):
            if s[i] == '(' and s[i+1] == ')':
                s_list.pop(i)
                s_list.pop(i+1)
                flag = 1
                break

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

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

op=0
cl=0

i=0
j=len(S)-1
while i<=j:
    if i==j:
        if S[i]=='(':
            cl+=1
        else:
            op+=1
        break
    while S[i]!='(' and i<len(S)-1:
        i+=1
        op+=1
    while S[j]!=')' and j>0:
        j-=1
        cl+=1
    if i<j:
        i+=1
        j-=1

r='('*op+S+')'*cl

print r

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    N = int(input())
    S = input()

    for i in range(50):
        tmpS = S.replace("()", "")

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

Solution code:
import re

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

Solution code:
n = int(input())
x = input()
s =[]
s += x
l,r = 0,0 #r = ( ; l = )
for i in range(n):
 if s[i] == '(':
  r += 1
 else :
  l += 1
if r - l > 0:
 s += [')']*(r-l)
if r-l < 0:
 s = ['(']*(l-r) + s[:]
if r-l == 0 and s[0] == ')':
 s = ['(']*int(n/2) + s[:] + [')']*int(n/2)
print(''.join(s))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
S1 = "".join(S.split(")("))
a = S1.count("(") - (S1[0] == "(") + (S1 != S)
b = S1.count(")") - (S1[-1] == ")") + (S1 != S)
print("(" * b + S + ")" * a)

Submission status: Wrong Answer

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(100):
    for j in xrange(100):
        T = "("*i + S + ")"*j
        if is_correct(T):
            print T
            flag = True
            break
    if flag:
        break

Submission status: Wrong Answer

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(')')
    print(*ans, sep='')

ans.extend(')' * st)

print(*ans, sep='')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    S = str(input())
    return (N, S)


def solve(N, S):
    ans = collections.deque([])
    count_curl = []
    count = 0
    now = S[0]
    for s in S:
        if s == now:
            count += 1
        else:
            count_curl.append((now, count))
            now = s
            count = 1
    else:
        count_curl.append((now, count))
    
    curl_len = len(count_curl)
    for i in range(curl_len):
        now = count_curl[i]
        if i == 0 and now[0] == ")":
            for __ in range(now[1]):
                ans.append("(")
            for __ in range(now[1]):
                ans.append(")")
            continue
        if now[0] == "(":
            for __ in range(now[1]):
                ans.append("(")
            for __ in range(now[1]):
                ans.append(")")
            continue
        elif now[0] == ")":
            pre = count_curl[i - 1]
            if now[1] > pre[1]:
                dif = now[1] - pre[1]
                for __ in range(dif):
                    ans.appendleft("(")
                for __ in range(dif):
                    ans.append(")")

    ans = "".join(ans)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

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

l = 0
ans = ''
tmp = ''
for s in S:
    if s == '(':
        if l >= 0:
            tmp += '('
            l += 1
        elif l < 0:
            tmp = '(' * (-l) + tmp
            ans += tmp
            tmp = '('
            l = 1

    elif s == ')':
        tmp += ')'
        l -= 1
        if l == 0:
            ans += tmp
            tmp = ''
else:
    if l > 0:
        tmp += ')' * l
    elif l < 0:
        tmp = '('*(-l) + tmp
    ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:

from itertools import combinations
from itertools import product
import bisect
import math

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

l = 0
ans = ''
tmp = ''
for s in S:
    if s == '(':
        if l >= 0:
            tmp += '('
            l += 1
        elif l < 0:
            tmp = '(' * (-l) + tmp
            ans += tmp
            tmp = '('
            l = 1

    elif s == ')':
        tmp += ')'
        l -= 1
        if l == 0:
            ans += tmp
            tmp = ''
    print(ans, tmp)
else:
    if l > 0:
        tmp += ')' * l
    elif l < 0:
        tmp = '('*(-l) + tmp
    ans += tmp

print(ans)

Submission status: Wrong Answer

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[i]+=")"
for i in ins:
    tmp[i]="("+tmp[i]
print "".join(tmp)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
cnt = [0, 0]
add = [0, 0]
ans = ''
for i in range(n):
    if s[i] == ')':
        cnt[0] += 1
        if cnt[0] > cnt[1]:
            add[0] += 1
    else:
        cnt[1] += 1

print('(' * add[0] + s + ')'*(cnt[1] -cnt[0] + add[0]))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
cnt = [0, 0]
add = [0, 0]
ans = ''
for i in range(n):
    if s[i] == ')':
        cnt[0] += 1
        if cnt[0] > cnt[1]:
            add[0] += 1
    else:
        cnt[1] += 1

print('(' * add[0] + s + ')'*(cnt[0] - cnt[1] - add[0]))

Submission status: Wrong Answer

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 = ''

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
for i in xrange(N-1, -1, -1):
    if S[i] == ')':
        tmp += 1
    else:
        tmp -= 1
        if tmp < 0:
            r += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def correct(X):
    st = []
    for c in X:
        if c == "(":
            st.append("(")
        elif c == ")":
            if len(st) == 0:
                return False
            st.pop(len(st)-1)
    return st == []
def f(X):
    q = [X]
    while q != []:
        x = q.pop(0)
        if correct(x):
            return x
        q.append("("+x)
        q.append(x+")")
int(input())
print(f(input()))

Submission status: Time Limit Exceeded

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

while len(S) > 0:
    if S .startswith(')') == True:
        T = '(' + T
        S = S[1:]
    if S .endswith('(') == True:
        T = T + ')'
        S = S[:-1]
    if S .startswith('()') == True:
        S = S[2:]
    if S .endswith('()') == True:
        S = S[:-2]

print(T)

Submission status: Time Limit Exceeded

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

while len(S) > 0:
    if S .startswith(')') == True:
        T = '(' + T
        S = S[1:]
    if S .endswith('(') == True:
        T = T + ')'
        S = S[:-1]
    if S .startswith('())') == True:
        S = S[2:]
    if S .endswith('()') == True:
        S = S[:-2]

print(T)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

while T.find('()') > -1:
	T.replace('()','')

a = T.count(')')
b = T.count('(')

ls = list(S)
ls.append(')' * b)
ls.reverse()
ls.append('(' * a)
ls.reverse()
print(''.join(ls))

Submission status: Accepted

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

Submission status: Accepted

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

add_left=0
add_right=0
for s in S:
  if s=="(":
    add_right+=1
  elif add_right==0:
    add_left+=1
  else:
    add_right-=1

print('(' * add_left + S + ')' * add_right)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = r = 0
L = ""
for i in S:
    if i == "(":
        l += 1
    else:
        r += 1
    if l < r:
        L += "("
        l += 1
R = ")"* (l-r)
print(L+S+R)

Submission status: Accepted

Solution code:
N = int(input())
motoS = input()
S = list(motoS)
start = 0
end = 0
for i in range(N):
    if S[i] == '(':
        end += 1
    else:
        end -= 1
    if end < 0:
        start += 1
        end = 0
print('('*start+motoS+')'*end)

Submission status: Accepted

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

now=0
sen=0

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

print("("*sen + s + ")"*now)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def IN_I(): return int(sys.stdin.readline().rstrip())
def IN_LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def IN_S(): return sys.stdin.readline().rstrip()
def IN_LS(): return list(sys.stdin.readline().rstrip().split())


N = IN_I()
S = IN_S()
d = deque(S)

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

r = 0
for i in range(N - 1, -1, -1):
    if S[i] == ')':
        r += 1
    else:
        if r == 0:
            d.append(')')
        else:
            r -= 1
print(''.join(d))

Submission status: Accepted

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

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

x = min(d)

s = '('*(-x) + s + ')'*(d[n]-x)
print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ss = s
while ss.count('()'):
    ss = ss.replace('()', '')
left, right = ss.count('('), ss.count(')')
print('(' * right + s + ')' * left)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
l = []
left, right = 0, 0
for c in s:
    if c == ')':
        if l == []:
            left += 1
        else:
            l.pop()
    else:
        l.append(1)
right = len(l)
print('(' * left + s + ')' * right)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n = I()
    s = S()

    cnt = 0
    right = 0
    
    for char in s:
        if char == "(":
            cnt += 1
        else:
            if cnt == 0:
                right += 1
            else:
                cnt -= 1

    ans = "("*right + s + ")"*cnt

    print(ans) 
    

        


main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
R, L = 0, 0
for i in range(len(s)):
    if s[i] == '(':
        R += 1
    else:
        if R:
            R -= 1
        else:
            L += 1

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cnt, L = 0, 0
for i in range(len(s)):
    if s[i] == '(':
        cnt += 1
    else:
        cnt -= 1

    if cnt < 0:
        L = min(L, cnt)

ans = '('*abs(L) + s
R = ans.count('(') - ans.count(')')
ans += ')'*R

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
T = list(1 if c == "(" else -1 for c in S)
l, l_min = 0, 0
r, r_min = 0, 0
for i in range(N):
    l += T[i]
    l_min = min(l_min, l)
    r -= T[N - i - 1]
    r_min = min(r_min, r)
print("".join(["(" * -l_min, S, ")" * -r_min]))

Submission status: Accepted

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

ans = []
count = 0
addFlag = True
for i in range(N):
    if addFlag:
        if S[i] == ')':
            ans.append(')')
            ans.insert(0,'(')
        else:
            ans.append('(')
            count += 1
            addFlag = False
    else:
        if S[i] == '(':
            ans.append('(')
            count += 1
        else:
            ans.append(')')
            count -= 1
            if count == 0:
                addFlag = True

for _ in range(count):
    ans.append(')')

print(''.join(ans))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
S = input()
left = 0
right = 0
for i in range(n):
    if S[i] == '(':
        right += 1
    elif S[i] == ')':
        if right >= 1:
            right -=1
        else:
            left += 1
print('('*left + S + ')'*right)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = input()
cr = 0
cl = 0
ans = a
for i in range(n):
  if a[i] == "(":
    cl += 1
  elif a[i] == ")":
    cr += 1
  if cl == 0 and cr != 0:
    ans = "(" + ans
    cr -= 1
  if cl != 0 and cr != 0:
    if cr >= cl:
      cl, cr = 0,cr-cl
    else:
      cl, cr = cl-cr,0
if cl != 0:
  for i in range(cl):
    ans = ans+")"
print(ans)

Submission status: Accepted

Solution code:
n = input()
cnt = 0
S = input()
m = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1
    m = min(m, cnt)

left = -min(0, m)
right = abs(cnt - m)
print("(" * left + S + ")" * right)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
c = 0
from collections import deque
res = deque([])
for i in range(n):
    if s[i] =='(':
        c += 1
    else:
        c -= 1
    if c < 0:
        res.appendleft('(')
        c = 0
    res.append(s[i])
if c > 0:
    res.append(')'*c)
print(''.join(list(res)))

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	S = input()
	brackets = [0, 0]
	for i in range(len(S)):
		if S[i] == ")":
			if brackets[0] > 0:
				brackets[0] -= 1
			else:
				brackets[1] += 1
		elif S[i] == "(":
			brackets[0] += 1
	print(brackets[1] * "(" + S + brackets[0] * ")")

main()

Submission status: Accepted

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

count = 0
new_left = 0
new_right = 0

for si in s:
    if si == '(':
        count += 1
    else:
        count -= 1

        if count == -1:
            count = 0
            new_left += 1

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
counter_l = 0
pairs = 0
double_check = set()

for i in range(n):
    if s[i] == "(":
        counter_l += 1
        for j in range(i + 1, n):
            if s[j] == ")" and j not in double_check:
                pairs += 1
                double_check.add(j)
                break
counter_r = n - counter_l
s = s + ")" * (counter_l - pairs)
s = "(" * (counter_r - pairs) + s

print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cnt_l, cnt_r = 0, 0

for x in s:
	if x == "(":
		cnt_l += 1
	elif cnt_l > 0:
		cnt_l -= 1
	else:
		cnt_r += 1

print(cnt_r * "(" + s + cnt_l * ")")

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cnt_l, cnt_r = 0, 0

for x in s:
	if x == "(":
		cnt_l += 1
	elif cnt_l > 0:
		cnt_l -= 1

for x in s[::-1]:
	if x == ")":
		cnt_r += 1
	elif cnt_r > 0:
		cnt_r -= 1

print(cnt_r * "(" + s + cnt_l * ")")

Submission status: Accepted

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

l = 0
r = 0
for si in s:
  if si == "(":
    r += 1
  else:
    if r == 0:
      l += 1
    else:
      r -= 1
ans = ""
for _ in range(l):
  ans += "("
ans += s
for _ in range(r):
  ans += ")"
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
mn=0
sm=0
for i in range(n):
  sm+=1 if s[i]=="(" else -1
  mn=min(mn,sm)
mn*=-1
print("("*mn+s+")"*(sm+mn))

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

N = cin()[0]
S = input()

tmp = S[::]
for i in range(100): tmp = tmp.replace("()", "")
cnt1 = 0
cnt2 = 0
for i in range(len(tmp)):
    if tmp[i] == '(': cnt1 += 1
    else: cnt2 += 1

ans = S[::]
ans = "(" * cnt2 + S + ')' * cnt1;
print(ans);

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

a=-m
b=x-m
print('('*a+S+')'*b)

Submission status: Accepted

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

l = 0
r = 0
for i in range(N):
    if S[i] == ")":
        r -= 1
        if r<0:
            l += 1
            r=0 #rを0に戻す作業
    else:
        r += 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N = read_ints()
    S = input().strip()
    opening = closing = 0
    left_add = 0
    for c in S:
        if c == '(':
            opening += 1
        else:
            closing += 1
        if closing > opening:
            left_add = max(left_add, closing-opening)
    opening = closing = 0
    right_add = 0
    for c in S[::-1]:
        if c == '(':
            opening += 1
        else:
            closing += 1
        if opening > closing:
            right_add = max(right_add, opening-closing)

    return '('*left_add+S+')'*right_add


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
N=int(input())
S=input()
R=[0 for i in range(N)]
L=[0 for i in range(N)]
LL=0
RR=0
for i in range(N):
  if S[i]=='(':
    LL+=1
  else:
    RR+=1
  L[i]=LL
  R[i]=RR
s=0
for i in range(N):
  s=max(s,R[i]-L[i])
t=s+L[N-1]-R[N-1]
print('('*s+S+')'*t)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=intput()
S=input()
tmp=0
ans=deque()
for i in range(N):
    c=S[i]
    tmp = tmp+1 if c=='(' else tmp-1
    if tmp<0:
        ans.appendleft('(')
        tmp=0
    ans.append(c)
for _ in range(tmp):
    ans.append(')')
ans=list(ans)
lprint(ans,'')

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    s = input()

    l = 0
    r = 0

    for i in s:
        if i == ")" and r > 0:
            r -= 1
        elif i == ")":
            l += 1
        if i == "(":
            r += 1
    print("("*l + s + ")"*r)




if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
closings = list(input())
r_cnt = l_cnt = 0
for closing in closings:
  if closing == ')':
    if l_cnt > 0:
      l_cnt -= 1
    else:
      r_cnt += 1
  else:
    l_cnt += 1
answer = ['(' for _ in range(r_cnt)] + closings + [')' for _ in range(l_cnt)] 
print(''.join(answer))

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    #solve
    right=0
    left=0

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

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

        if opens < 0:
            l += 1
            opens = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    S = input()
    stack = []
    for s in S:
        if not stack:
            stack.append(s)
        elif s == "(":
            stack.append(s)
        elif s == ")":
            if stack[-1] == "(":
                stack.pop()
            else:
                stack.append(s)
    cnt = defaultdict(int)
    for s in stack:
        cnt[s] += 1
    left = cnt[")"]
    right = cnt["("]
    ans = ("(" * left) + S + (")" * right)
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = S
count = 0

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

count = 0

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

    if(count>0):
        ans = ans + ")"
        count -= 1

print(ans)

Submission status: Accepted

Solution code:
with open(0) as f:
    N, S = f.read().split()
N = int(N)
S += '_'
left = 0
right = 0
cnt = 0
for i in range(N):
    cnt += {'(':1, ')':-1}[S[i]]
    if S[i] == ')' and S[i+1] != ')':
        if cnt < 0:
            left += -cnt
            cnt = 0
    if i == N-1 and cnt > 0:
        right += cnt
ans = '(' * left + S[:N] + ')' * right
print(ans)

Submission status: Accepted

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

keep = 0
ans = ''
for i in range(N):
    if s[i] == '(':
        ans += '('
        keep += 1
    else:
        if keep > 0:
            ans += ')'
            keep -= 1
        else:
            ans = ('(' + ans + ')')
print(ans + ')' * keep)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    l, r, c = 0, 0, 0
    for a in s:
        if a == '(':
            c += 1
        elif c:
            c -= 1
        else:
            l += 1
    r = c
    print("("*l + s + ")"*r)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    l, r, c = 0, 0, 0
    for a in s:
        if a == '(':
            c += 1
        else:
            if c:
                c -= 1
            else:
                l += 1
    r = c
    print("("*l + s + ")"*r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
s = input()
def f(s):
    d = 0
    for i in range(len(s)):
        if s[i] == "(":
            d += 1
        else:
            d -= 1
        if d < 0:
            return "("+s
    if d > 0:
        return s+")"
    else:
        print(s)
        exit(0)
while True:
    s = f(s)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=[]
for i in s:
  if i==')':
    if len(l)>0:
      if l[-1]=='(':
        l.pop()
      else:
        l.append(i)
    else:
      l.append(i)
  else:
    l.append(i)
print(l.count(')')*'(' + s +l.count('(')*')')

Submission status: Accepted

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

cnt_rgt = 0
cnt = 0
for i in range(len(S)):
    if S[i]=="(":
       cnt += 1
    if S[i]==")":
        cnt -= 1
        if cnt<0:
            cnt = 0
            cnt_rgt += 1

rgt = "("*cnt_rgt
lft = ")"*cnt

print(rgt+S+lft)