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:
def main():
    n = int(input())
    s = input()
    l, r = 0, 0
    for c in s:
        if c == '(':
            l += 1
        else:
            if l:
                l -= 1
            else:
                r += 1
    print('(' * r + s + ')' * l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
c = 0
d = 0
for i in range(n):
    if s[i] == '(':
        c += 1
    else:
        d += 1
used_c = [True]*n
used_d = [True]*n
for i in range(n):
    if s[i] == '(':
        for j in range(i+1, n):
            if s[j] == ')' and used_c[j]:
                c -= 1
                used_c[j] = False
                break
    else:
        for j in range(i):
            if s[j] == '(' and used_d[j]:
                d -= 1
                used_d[j] = False
                break
print('('*d+s+')'*c)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    N = int(input())
    s = input()

    ans = deque(s)
    cnt = 0
    for c in s:
        if c == ')':
            if cnt:
                cnt -= 1
            else:
                ans.appendleft('(')
        else:
            cnt += 1

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

    print(''.join(ans))


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
N=int(input())
S=input()
n_left=0
n_right=0
for a in S:
    if a==")":
        if n_left==0:
            n_right+=1
        else:
            n_left-=1
    else:
        n_left+=1
print((n_right*"(")+S+(n_left*")"))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
 
f = 0
b = 0
count = 0
for i in range(N - 1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1
 
print('(' * count, end='')
print(*S, sep='', end='')
print(')' * b)

Submission status: Accepted

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

f = 0
b = 0
count = 0
for i in range(N - 1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1
    
print ('(' * count, end = '')
print (*S, sep = '', end = '')
print (')' * b)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = 0
r = 0
for c in S:
    if c == '(':
        l += 1
    else:
        if l != 0:
            l -= 1
        else:
            r += 1
print('('*r + S + ')'*l)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
ans = ''
cnt = 0
for c in s:
    ans += c
    if c == ')':
        cnt -= 1
    else:
        cnt += 1
    if cnt < 0:
        ans = '(' + ans
        cnt = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

if L > R:
    S = S + (')' * (L - R))
if R > L:
    S = ('(' * (R - L)) + S

d = 0
mx = 0
for s in S:
    if s == ')':
        d += 1
    else:
        d -= 1
    mx = max(mx, d)

S = '(' * mx + S + ')' * mx
print(S)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ans1=0
maxans=0
def split(word): 
    return [char for char in word]  
def convert(s): 
  
    # initialization of string to "" 
    new = "" 
  
    # traverse in the string  
    for x in s: 
        new += x  
  
    # return string  
    return new 
for i in range(N):
  if S[i]=='(':
    ans1-=1
  else:
    ans1+=1
    if ans1>maxans:
      maxans=ans1
ans2=0
minans=0
for i in range(N):
  if S[N-1-i]==')':
    ans2-=1
  else:
    ans2+=1
    if ans2>minans:
      minans=ans2
r=split(S)
for i in range(minans):
  r.append(')')
r.reverse()
for i in range(maxans):
  r.append('(')
r.reverse()
print(convert(r))

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
S1 = S
cur = 0
for i in range(len(S)):
    if S[i]=="(":
        cur += 1
    else:
        cur -= 1
    if cur<0:
        S1 = "("+S1
        cur += 1
S1 = S1+")"*cur
print(S1)

Submission status: Accepted

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

p=0
q=0
for i in s:
  if i=='(':
    p+=1
  else:
    if p>=1:
      p-=1
    else:
      q+=1
      p=0

ans='('*q+s+')'*p
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc064/tasks/abc064_d
# カッコこっかを対応させたい → 前か後ろに追加するだけで良い


def n_fusoku(S, target='('):  # 順方向で書いておく (を先頭に追加すべき個数
    stack = []
    ret = 0
    for s in S:
        if s == target:
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                ret += 1  # 不足分
    return ret


N = read_a_int()
S = input()
n_kakko = n_fusoku(S)
n_kokka = n_fusoku(reversed(S), target=')')
print('(' * n_kakko + S + ')' * n_kokka)

Submission status: Accepted

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

max_k = 0
now = 0
for s in sl:
    if s == "(":
        now += 1
    else:
        now -= 1
    max_k = min(now, max_k)


print("(" * (-max_k) + "".join(sl) + max(now-max_k, 0) * ")")

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
l_ins = 0
l = 0
r = 0
for i in range(n):
    if s[i] == "(":
        l += 1
    else:
        r += 1
    l_ins = max(l_ins, r-l)
r_ins = 0
l = 0
r = 0
for i in range(n-1, -1, -1):
    if s[i] == "(":
        l += 1
    else:
        r += 1
    r_ins = max(r_ins, l-r)
ar = ["("]*l_ins + s + [")"]*r_ins
print("".join(ar))

Submission status: Accepted

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

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

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

print("(" * left + S + ")" * right)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    s = input()
    left = 0
    stack = deque([])
    for ss in s:
        if ss == "(":
            stack.append("(")
        elif not stack:
            left += 1
        else:
            stack.pop()
    print(left * "(" + s + len(stack) * ")")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = s
while "()" in t:
    t = t.replace("()", "")

a = t.count(")"); b = t.count("(")

print("(" * a + s + ")" * b)

Submission status: Accepted

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

need_left = 0
pointer = 0
for i in range(len(S)):
    if S[i] == '(':
        pointer += 1
    else:
        if pointer == 0:
            need_left += 1
        else:
            pointer -= 1
need_right = pointer

res = "(" * need_left + S + ")" * need_right
print(res)

Submission status: Accepted

Solution code:
# 解説解法

# ちゃんとした括弧列 s=(s1,...,sn):
# - '('と')'の個数は等しい
# - 任意のprefixにおいて，'('の個数 >= ')'の個数 (これがないと閉じない)
#
# di = (s1,...,si)の '('の個数 - ')'の個数
# x = min(d1, ..., dn)
# 
# '('を1つ入れる → dnは1増える xは0 or 1増える (場所による)
# ')'を1つ入れる → dnは1減る xは0 or 1減る (場所による)
#
# 2つの値(a=dn, b=x)を管理する
#
# 4つの操作を考える
#  [a] a += 1
#  [b] a += 1, b += 1
#  [c] a -= 1
#  [d] a -= 1, b -= 1
#
# - b <= 0 から b == 0にしないといけないので，[b]を-b回行う (dはムダなのでやらない)
# - aの値が a + bになっている， a >= bよりa >= 0
# - 次にaを0にしたい．そのため，cを a + b回やる
# - つまり挿入回数は a - 2b = dn - x 回数未満
#
# 構成法
# - 一番左に '(' を -x 回
# - 一番右に ')' を dn - x回

n = int(input())
s = list(input())
# d = []
# co, cc = 0, 0
# for ch in s:
#     if ch == '(':
#         co += 1
#     elif ch == ')':
#         cc += 1
#     d.append(co - cc)

# # 計算
# x = min(d)

# str_left = '(' * (-x)
# str_right = ')' * (d[-1] - x)

# print("{}{}{}".format(str_left, "".join(s), str_right))


co, cc = 0, 0
for ch in s:
    if ch == '(':
        co += 1
    if ch == ')':
        if co > 0:
            co -= 1
        else:
            cc += 1

ans = "(" * cc + "".join(s) + ")" * co
print(ans)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


def main():
    _ = int(input())
    S = input()

    T = []
    cnt = 0
    for s in S:
        if s == ')' and cnt == 0:
            T = ['('] + T + [')']
        elif s == ')' and cnt > 0:
            T = T + [')']
            cnt -= 1
        else:
            T = T + ['(']
            cnt += 1

    T = ['(' if t == ')' else ')' for t in T]
    new_S = T[::-1]

    T = []
    cnt = 0
    for s in new_S:
        if s == ')' and cnt == 0:
            T = ['('] + T + [')']
        elif s == ')' and cnt > 0:
            T = T + [')']
            cnt -= 1
        else:
            T = T + ['(']
            cnt += 1

    T = ['(' if t == ')' else ')' for t in T]
    T = T[::-1]
    print(''.join(T))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    S=input()
    a,b=0,0
    for i in range(N):
        if S[i]=='(':
            b+=1
        else:
            if b==0:
                a+=1
            else:
                b-=1
    print('('*a+S+')'*b)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
import copy
ss = copy.deepcopy(s)
import heapq

aa = []
bb = []
a,b,c = 0,0,0
for i in range(n):
    if s[i] == ")":
        c += 1
    
    if s[i] == "(":
        a += 1
        for j in range(i+1,n):
            if s[j] == ")":
                b += 1
                s = s[:j] + "-" + s[j+1:]
                break
            
ans = "("*c + ss + ")"*(a-b)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
left = 0
right = 0
cnt1 = 0
for i in S:
    if i == '(':
        left += 1
    else:
        right += 1
    cnt1 = max(cnt1, right - left)
left = 0
right = 0
cnt2 = 0
for i in S[::-1]:
    if i == ')':
        left += 1
    else:
        right += 1
    cnt2 = max(cnt2, right - left)
ans = '(' * max(0, cnt1) + S + ')' * max(0, cnt2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
nl = 0
nr = 0
for i in S:
    if i == ')':
        if nr > 0:
            nr -= 1
        else:
            nl += 1
    else:
        nr += 1
print('('*nl + S + ')'*nr)

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = list(input())
    answer = ""
    right = 0
    left = 0
    for s in S:
        if s == "(":
            if right > 0:
                answer = "(" * right + answer
                answer += ")" * right
                right = 0
            left += 1
            answer += "("
        else:
            if left > 0:
                answer += ")"
                left -= 1
            else:
                right += 1
    if left > 0:
        answer += ")" * left
    if right > 0:
        answer = "(" * right + answer + ")" * right
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# solution
import io
import math

data = int(input())
inin = input()

a1 = 0
a2 = 0

for i in range(data):
    if inin[i] == '(':
        a1 += 1
    else:
        if a1 > 0:
            a1 -= 1
        else:
            a2 += 1
print('('*a2+inin+')'*a1)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
cnt = 0
for i in range(n-1, -1, -1):
    if s[i] == ')':
        cnt += 1
    elif cnt > 0:
        cnt -= 1
s = cnt*'(' + ''.join(s)
cnt = 0
for i in range(len(s)):
    if s[i] == '(':
        cnt += 1
    else:
        cnt -= 1       
print(s+')'*cnt)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = list(input())
T = deque(S[:])
ins = []
pointer = 0
a = 0
for i in range(N):
  if S[i] == ')':
    if pointer >= 1:
      pointer -= 1
    else:
      T.appendleft('(')
  else:
    pointer += 1
  
a = 0
b = 0
for t in T:
  if t == ')':
    b += 1
  else:
    a += 1

for i in range(max(a-b, 0)):
  T.append(')')
print(''.join(T))

Submission status: Accepted

Solution code:
## coding: UTF-8

N = int(input())
s = input()
l = []
AB = []
for i in range(N):
    l.append(s[i])
    if(s[i] == '('):
        AB.append('A')
    else:
        AB.append('B')


#print(AB)
first_A_lack_counter = 0
last_B_lack_counter = 0

mode = 'even' 
#even, A_lack, B_lack

index = 0
while True:
    #print()
    #print('index:{}, AB[index]:{}'.format(index, AB[index]))
    if(mode == 'even'):
        if(AB[index] == 'A'):
            mode = 'B_lack'
            last_B_lack_counter += 1
            #print('mode change even->B_lack')
        elif(AB[index] == 'B'):
            mode = 'A_lack'
            first_A_lack_counter += 1
            #print('mode change even->A_lack')
    elif(mode == 'A_lack'):
        if(AB[index] == 'A'):
            mode = 'B_lack'
            last_B_lack_counter = 1
            #print('mode change A_lack->B_lack')
        elif(AB[index] == 'B'):
            first_A_lack_counter += 1
            #print('first_A_lack_counter:{}'.format(first_A_lack_counter))
    elif(mode == 'B_lack'):
        if(AB[index] == 'A'):
            last_B_lack_counter+= 1
            #print('last_B_lack_counter:{}'.format(last_B_lack_counter))
        elif(AB[index] == 'B'):
            last_B_lack_counter -= 1
            #print('last_B_lack_counter:{}'.format(last_B_lack_counter))
        if(last_B_lack_counter == 0):
            mode = 'even'
            #print('mode change B_lack->even')
    #print()
    index += 1
    if(index == N):
        break
#print('first_A_lack:{}'.format(first_A_lack_counter))
#print('last_B_lack:{}'.format(last_B_lack_counter))

#print()
#print()
#print(l)

first_A = []
for i in range(first_A_lack_counter):
    first_A.append('(')
l = first_A + l

for i in range(last_B_lack_counter):
    l.append(')')

#print(l)
print('{}'.format(''.join(l)))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = IN()
	s = input()
	rc=0
	rc_max=0
	for c in s:
		if c == ')':
			rc+=1
			rc_max=max(rc_max, rc)
		else:
			rc -= 1
	
	lc=0
	lc_max=0
	for c in s[::-1]:
		if c == '(':
			lc += 1
			lc_max=max(lc, lc_max)
		else:
			lc -= 1
	ret = '(' * rc_max + s + ')'*lc_max
	print(ret)
			
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n=int(input());s=input()
ans = '';v = 0;vmin = 0
for s0 in s:
    if s0 == '(':
        v += 1
    else:
        v -= 1
        vmin = min(v,vmin)
left = '('; right = ')'
if vmin < 0:
    ans += left*(-1*vmin)
    v += (-1*vmin)
if v == 0:
    ans += s
elif v > 0:
    ans += s + right*v
else:
    ans += left*(-1*v) + s
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input().rstrip()
t=""
d=0
for i in range(N):
  if S[i]=="(":
    d+=1
    t+="("
  else:
    if d>0:
      t+=")"
      d-=1
    else:
      t="("+t+")"
if d>0: t+=")"*d
else: t="("*(-d)+t
print(t)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
hidari = 0
migi = 0
for i in range(N):
  if S[i] == '(':
    hidari += 1
  else:
    if hidari > 0:
      hidari -= 1
    else:
      migi += 1
S = '(' * migi + S + ')' * hidari
print(S)

Submission status: Accepted

Solution code:
n=int(input())
kakko=[1 if i == '(' else -1 for i in list(input())]
tmp=0
x=0
y=0
for i in range(n):
    x+=kakko[i]
    if tmp<abs(x) and x<0:
        tmp+=1
kakko=[1]*tmp+kakko

if sum(kakko)>0:
    tmp=sum(kakko)
    kakko=kakko+[-1]*tmp
ans=['(' if i==1 else ')' for i in kakko]
print(''.join(ans))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
prel=0
prer=0
for s in S:
  if s=="(":
    prel+=1
  if s==")":
    if prel>0:
      prel-=1
    else:
      prer+=1
#print(prel,prer)
print(prer*"("+S+prel*")")

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0
r=0
for i in range(n):
  if r==0 and s[i]==')':
    l+=1
  elif s[i]=='(':
    r+=1
  elif r>0 and s[i]==')':
    r-=1
print('('*l+s+')'*r)

Submission status: Accepted

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
for i in range(len(leng2)):
    if leng2[i][0] == "(":
        lc += leng2[i][1]
    else:
        rc += leng2[i][1]
    if rc - lc > 0:
        leng[0][1] += rc-lc
        lc = 0
        rc = 0
leng[-1][1] += lc-rc

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: Accepted

Solution code:
from collections import defaultdict
n = int(input())
s = input()
ans = ""
cnt1=cnt2=cnt3=0
tmp = ""
for i in s:
    if i==")":

        if cnt2==0:
            cnt1+=1
            tmp+="("
            ans+=")"
        if cnt2>0:
            cnt2-=1
            ans+=")"

    if i=="(":
        cnt1=0
        cnt2+=1
        ans+="("
        if len(tmp)>0:
            ans = tmp+ans
            tmp=""

if cnt1>0:
    ans = "("*cnt1+ans
if cnt2>0:
    ans += ")"*cnt2
print(ans)

Submission status: Accepted

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

l = S.count('(')
r = S.count(')')
d = r - l

if d > 0:
    S = '(' * d + S
if d < 0:
    S = S + ')' * (-d)

l, r, d = 0, 0, 0
for s in S:
    if s == '(':
        l += 1
    if s == ')':
        r += 1
    d = max(d, r - l)

if d > 0:
    S = '(' * d + S + ')' * d

print(S)

Submission status: Accepted

Solution code:
n, s = int(input()), input()
mx, lt, rt = [0]*3
for i in range(n):
        if s[i]=="(": lt += 1
        else: rt += 1
        mx = max(mx, rt-lt)
print("("*mx + s + ")"*(lt+mx-rt))

Submission status: Accepted

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

while True:
    check = 0
    for i in range(len(s)):
        if s[i] == "(":
            check += 1
        else:
            check -= 1
            
        if check < 0:
            s.insert(0, "(")
            break
    else:
        for _ in range(check):
            s.append(")")
        print("".join(s))
        break

Submission status: Accepted

Solution code:
N=int(input())
S=input()
c1,c2=0,0
for s in S:
    if s=='(': c1+=1
    elif c1>0: c1-=1
for s in reversed(S):
    if s==')': c2+=1
    elif c2>0: c2-=1
print('('*c2 + S + ')'*c1)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
T = S
for i in range(100):
    for j in range(n):
        if j+1 < len(S) and S[j] == '(' and S[j+1] == ')':
            S = S[:j]+S[j+2:]
a = S.count('(')
b = S.count(')')
print('('*b+T+')'*a)

Submission status: Accepted

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

ret_left = 0

left = 0
for s in S:
    if s == ")":
        if left == 0:
            ret_left += 1
        else:
            left -= 1
    else:
        left += 1
        
ret_right = left

for i in range(ret_left):
    print("(", end = "")
print(S, end = "")
for i in range(ret_right):
    print(")", end = "")

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    le, ri = 0, 0
    addle, addri = 0, 0
    for s in S:
        if s == ")":
            le += 1
            if le <= ri:
                le -= 1
                ri -= 1
            else:
                le -= 1
                addri += 1
        elif s == "(":
            ri += 1
    addle = ri
    print("("*addri + S + ")"*addle)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    havePair = [False] * N
    rightN = 0
    leftLeft = 0
    ri = deque()
    for i in range(N):
        if S[i] == "(": 
            rightN += 1
            ri.append(i)
        else:
            if ri:
                rmin = ri.popleft()
                rightN -= 1
            else: leftLeft += 1

    Ans = ["(" * leftLeft, S, ")" * rightN]
    print("".join(Ans))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
op = 0
for c in S:
    if c=='(':
        op += 1
    elif op > 0:
        op -= 1
cl = 0
for c in S[::-1]:
    if c==')':
        cl += 1
    elif cl > 0:
        cl -= 1

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

Submission status: Accepted

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

ans = s
ans = list(ans)

cum = 0
for i in range(n):
    if s[i] == '(':
        cum += 1
    else:
        cum -= 1
    if cum < 0:
        ans = ['('] + ans
        cum = 0
else:
    ans = ans + [')']*cum

print(''.join(ans))

Submission status: Accepted

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

level = [0] * (N + 1)
level_tmp = 0
for i in range(N):
    level_tmp += (1 if S[i] == '(' else -1)
    level[i + 1] = level_tmp

# print("#", level)

left = '(' * max(0, -1 * min(level))
right = ')' * max(0, level[-1] + max(0, -1 * min(level)))

print(left + S + right)

Submission status: Accepted

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

    left = 0
    right = 0
    for c in s:
        if c == '(':
            right += 1
        else:
            if right > 0:
                right -= 1
            else:
                left += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

def solve():
    i = 0
    opens = []
    inspos = 0
    while i < len(S):
        if S[i] == '(':
            opens.append(i)
        elif opens:
            opens.pop()
        else:
            S.insert(inspos, '(')
            i += 1
        i += 1
    for _ in range(len(opens)):
        S.append(')')

solve()
print(''.join(S))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = 0
r = 0
count = 0
need = 0
for i in range(n):
    if s[i] == "(":
        l += 1
        count += 1
    else:
        r += 1
        if count > 0:
            count -= 1
        else:
            need += 1
print("(" * need + s + ")" * (l + need - r))

Submission status: Accepted

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

left_num = 0
right_num = 0

for i in range(N):
    if S[i] == '(':
        right_num += 1
    else:
        if right_num > 0:
            right_num -= 1
        else:
            left_num += 1

ans = '('*left_num + S + ')'*right_num
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
n=int(input())
s=input()
cnt=0
M=0

for i in s:
    if i==")":
        cnt+=1
    else:
        cnt-=1
    M=max(M,cnt)

print("("*M+s+")"*(M-cnt))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    s = list(input())
    right_parentheses = 0
    needed_right_parentheses = 0
    for i in s:
        if i == '(':
            right_parentheses += 1
        else:
            if right_parentheses > 0:
                right_parentheses -= 1
            else:
                needed_right_parentheses += 1

    ans = ['('] * needed_right_parentheses + s + [')'] * right_parentheses
    print(''.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
a = '('
b = ')'

i = 0
cntA = 0
ans = S
for s in S:
    if s == a:
        cntA += 1
    else:
        if cntA == 0:
            ans = '(' + ans
        else:
            cntA -= 1
else:
    ans = ans + ')' * cntA

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n = int(input())
    s = list(input())

    stack = []
    ans = deque([])
    for c in s:
        if c == '(':
            ans.append('(')
            stack.append('(')
        
        if c == ')':
            if stack==[]:
                ans.appendleft('(')
                ans.append(')')
            else:
                stack.pop()
                ans.append(')')
    for c in stack:
        ans.append(')')

    for c in ans:
        print(c,end="")
    print()

if __name__ == "__main__":
    main()

Submission status: Accepted

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

left = 0
right = 0

for i in range(N):
    if right == 0 and S[i] == ')':
        left += 1
    elif S[i] == '(':
        right += 1
    elif right > 0 and S[i] == ")":
        right -= 1
        
print("("*left + S + ")"*right)

Submission status: Accepted

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

s = remove(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: Accepted

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

open_left=0
open_right=0
for c in S:
    if c == ')':
        if open_left > 0:
            open_left -= 1
        else:
            open_right += 1
    else:
        open_left += 1
#print('(', open_left, ')', open_right)

ans = '('*open_right + S + ')' * open_left
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = input()

stack = []
que = deque()
for i in range(n):
    t = s[i]
    if t == '(':
        que.append('(')
        stack.append('(')
    else: # ')'
        if stack and stack[-1] == '(':
            stack.pop()
            que.append(')')
        else:
            que.appendleft('(')
            que.append(')')
            # stack.append(t)

ans = ''.join(que) + ')' * len(stack)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
s = list(input())
que = deque()
stack = []

for i in range(n):
    t = s[i]
    if t == '(':
        stack.append(t)
        que.append(t)
    else: # t == ')'
        if stack:
            if stack[-1] == '(':
                stack.pop()
                que.append(')')
            else:
                stack.append(')')
        else:
            que.appendleft('(')
            que.append(')')

print(''.join(que) + ')' * len(stack))