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())
S = list(input())

r_cnt, l_cnt = 0, 0

for s in S[::-1]:
    if s == ')':
        r_cnt += 1
    else:
        r_cnt = max(r_cnt-1, 0)

S = ['(']*r_cnt + S

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

S = S + [')']*l_cnt

print(*S, sep='')

Submission status: Accepted

Solution code:
def main():
    length = int(input())
    string = input()
    count = [0] * length
    min_value = 0
    for i in range(length):
        if i == 0:
            if string[i] == "(":
                count[i] = 1
            else:
                count[i] = -1
        elif string[i] == "(":
            count[i] = count[i - 1] + 1
        else:
            count[i] = count[i - 1] - 1
        min_value = min(min_value, count[i])
    print("(" * (-min_value) + string + ")" * (count[-1] - min_value))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = 0
cnt = 0
for s in S:
	if s=='(':
		cnt += 1
	else:
		if cnt>0:
			cnt -= 1
		else:
			l += 1

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

Submission status: Accepted

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

l = 0
r = 0
for si in s:
    if si == "(":
        l  += 1
    else:
        if l == 0:
            r += 1
        else:
            l -= 1

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

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
stack = []
ans = S[::1]
r = 0
for c in S:
    if c == "(":
        r += 1
    if c == ")":
        if r > 0:
            r -= 1
        else:
            ans.insert(0, "(")
for _ in range(r):
    ans.append(")")
print("".join(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
stack = []
ans = S[::1]
add = 0
r, l = 0, 0
for i in range(N):
    c = S[i+add]
    if c == "(":
        r += 1
    if c == ")":
        if r > 0:
            r -= 1
        else:
            ans.insert(0, "(")
for _ in range(r):
    ans.append(")")
print("".join(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())[::-1]
stack = []
ans = S[::1]
add = 0
r, l = 0, 0
for c in S:
    if c == ")":
        l += 1
    if c == "(":
        if l > 0:
            l -= 1
        else:
            ans.insert(0, ")")
for i in range(l):
    ans.append("(")
print("".join(ans[::-1]))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
begin = 0
end = 0
for i in range(n):
    if s[i] == "(":
        begin += 1
    if s[i] == ")":
        if begin > 0:
            begin -= 1
            continue
        end += 1
print("("*end + s + ")"*begin)

Submission status: Accepted

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

cnt1=0
cnt2=0
for i in range(n):
    if s[i]=='(':
        cnt1+=1
    else:
        if cnt1>0:
            cnt1-=1
        else:
            cnt2+=1
print('('*cnt2+s+')'*cnt1)

Submission status: Accepted

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

a=0
b=0

for i in s:
  if i=='(':
    a+=1
  else:
    if a!=0:
      a-=1
    else:
      b+=1

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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=s
s+='#'

c=s.count('()')
while c!=0:
  s=list(s)

  i=0
  n_s=''
  while i<=len(s)-1:
    if s[i]=='(' and s[i+1]==')':
      i+=2
    else:
      n_s+=s[i]
      i+=1

  s=''.join(n_s)
  c=s.count('()')

c_a=s.count('(')
c_b=s.count(')')

ans='('*c_b+ans+')'*c_a
print(ans)

Submission status: Accepted

Solution code:
N, S = open(0).read().split()
N = int(N)
cnt = 0
l = 0
for i in range(N):
  if S[i]=='(':
    cnt += 1
  else:
    if cnt==0:
      l += 1
    else:
      cnt -= 1
cnt = 0
r = 0
for i in range(N-1,-1,-1):
  if S[i]==')':
    cnt += 1
  else:
    if cnt==0:
      r += 1
    else:
      cnt -= 1
print('('*l+S+')'*r)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

s = input().split()[0]

ss = ""
co = 0
for i in range(n):
    if s[i] == ")" and co <= 0:
        ss = "(" + ss + ")"
    elif s[i] == ")":
        ss = ss + ")"
        co -= 1
    if s[i] == "(":
        co += 1
        ss = ss + "("
print(ss + ")" * co)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
li=list(s)
leftWhichNeedsRight = [] # )
RightWhichNeedsLeft = [] # ()
if li[0] == "(":
    leftWhichNeedsRight.append(1)
    RightWhichNeedsLeft.append(0)
if li[0] == ")":
    leftWhichNeedsRight.append(0)
    RightWhichNeedsLeft.append(1)
for i in range(1,n):
    c = li[i]
    l = leftWhichNeedsRight[i-1]
    r = RightWhichNeedsLeft[i-1]
    if c == "(":
        RightWhichNeedsLeft.append(r)
        leftWhichNeedsRight.append(l+1)
    elif c == ")":
        if l > 0:
            RightWhichNeedsLeft.append(r)
            leftWhichNeedsRight.append(l-1)
        else:
            RightWhichNeedsLeft.append(r+1)
            leftWhichNeedsRight.append(l)
# print(RightWhichNeedsLeft)
# print(leftWhichNeedsRight)
print("("*RightWhichNeedsLeft[n-1]+s+")"*leftWhichNeedsRight[n-1])

Submission status: Accepted

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

Submission status: Accepted

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

count = 0
left_num = 0

for p in parentheses:
    if p == '(':
        count += 1
    else:
        count -= 1

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

print('(' * left_num + parentheses + ')' * count)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
s = readline().rstrip().decode('utf-8')

"""
左端に(を、右端に)を必要なだけ与えることで辞書順最小になる
"""

eight = 0
nine = 0
flag = 0
th = 0
res = 0
for i in s:
    if i == ")":
        if th:
            th -= 1
        else:
            res += 1
    elif i == "(":
        th += 1
res2 = 0
th = 0
for i in s[::-1]:
    if i == "(":
        if th:
            th -= 1
        else:
            res2 += 1
    elif i == ")":
        th += 1

s = "("*res + s + ")"*res2
print(s)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    S = input()
    lc,rc = 0,0
    for s in S:
        if s == "(":
            rc += 1
        else:
            if rc <= 0:
                lc += 1
            else:
                rc -= 1
    
    print("("*lc+S+")"*rc)            
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    S = str(input())
    left,right = 0,0
    for s in S:
        if s == "(":
            right += 1
        elif right <= 0:
            left += 1
        else:
            right -= 1
        
    print("("*left+S+")"*right)
  
if __name__ == "__main__":
    main()

Submission status: Accepted

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

l_num, r_num = 0, 0
for i in s:
    if i == '(':
        l_num += 1
    elif l_num <= 0:
        r_num += 1
    else:
        l_num -= 1
print('(' * r_num + s + ')' * l_num)

Submission status: Accepted

Solution code:
import copy
N = int(input())
S = input()
stack = []
ans = copy.deepcopy(S)
for s in S:
    if s == ")":
        if len(stack) > 0 and stack[-1] == "(":
            stack.pop()
        else:
            ans = "(" + ans
    elif s == "(":
        stack.append(s)
for _ in range(len(stack)):
    ans = ans + ")"
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    S=ST()
    head = 0
    tail = 0
    c,e = 0,0
    for s in S:
        if s=="(":
            c += 1
        else:
            e += 1
        if c<e:
            head += e-c
            e=c
    if c>e:
        tail = c-e
    print(head * "(" + S + tail * ")")
        
if __name__ == '__main__':
    main()
    #H*W = Sになるような最大値最小の(H,W)を求める
    # S=I()
    # x1,y1 = 0,0
    # x2,y3 = 0,0

    # x2,y2


    # S=ST()
    # ans = 0
    # for i in range(len(S)):
    #     for it in combinations([i for i in range(len(S))], i):
    #         before = 0
    #         for j in it:
    #             print(int(S[before:j+1]), before,j)
    #             ans += int(S[before:j+1])
    #             before = j+1
    #         try:
    #             ans += int(S[before:])
    #         except:
    #             pass
    #         print(ans)
    # print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(str, input()))

# 相手がいない()をカウントすればいい
left_stock = 0
left_short = 0

for s in S:
	if s == "(":
		left_stock += 1
	else:
		if left_stock > 0:
			left_stock -= 1
		else:
			left_short += 1
			
for _ in range(left_short):
	print("(", end = "")
for s in S:
	print(s, end = "")
for _ in range(left_stock):
	print(")", end = "")

Submission status: Accepted

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

RLE = []
now_char = S[0]
now_cnt = 1
for i in range(1, N):
    if now_char == S[i]:
        now_cnt += 1
    else:
        RLE.append([now_char, now_cnt])
        now_char = S[i]
        now_cnt = 1
RLE.append([now_char, now_cnt])


n = len(RLE)
ans = ""
left_cnt = 0
right_cnt = 0

for i in range(n):
    now_char = RLE[i][0]
    now_cnt = RLE[i][1]
    if now_char == "(":
        left_cnt += now_cnt
    else:
        right_cnt += now_cnt
        if right_cnt > left_cnt:
            ans += "(" * (right_cnt - left_cnt)
            right_cnt = 0
            left_cnt = 0
        else:
            left_cnt -= right_cnt
            right_cnt = 0

ans += S
if left_cnt > 0:
    ans += ")" * left_cnt

print(ans)

Submission status: Accepted

Solution code:
import copy

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

ans = copy.copy(s)

lens = 0
while lens != len(s):
    lens = len(s)
    for i in range(len(s)):
        if s[i:i+2] == '()':
            s = s[:i] + s[i+2:]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
s=input()
i=0
leftcnt=0
rightcnt=0
for i in range(len(s)):
    if s[i]==")":
        if leftcnt==0:
            rightcnt+=1
        else:
            leftcnt-=1
    else:
        leftcnt+=1
print("("*rightcnt+s+")"*leftcnt)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    S2 = S

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

    x = S2.count("(")
    y = S2.count(")")

    print(y * "(" + S + x * ")")




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
s = S
l=0
r=0
tmp=0
flag = True
for i in range(N):
    #始めて(が出てくるインデックス
    if S[i]=="(":
        tmp=i
        r=1
        flag = False
        break
    else:
        l += 1
#tmp=N-1の場合は別でやる必要あり
"""
if tmp==(N-1):
    s = s+")"
"""
if not flag:
    for i in range(tmp+1,N):
        if S[i]=="(":
            r+=1
        else:
            if r>0:
                r-=1
            else:
                l+=1

if r>0:
    for _ in range(r):
        s = s + ")"

if l>0:
    for _ in range(l):
        s = "(" + s

print(s)

Submission status: Accepted

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

l_lack=0
l_cnt=0

for tmp in s:
    if tmp==")":
        if l_cnt==0:
            l_lack+=1
        else:
            l_cnt-=1
    if tmp=="(":
        l_cnt+=1

left="("*l_lack
right=")"*l_cnt
print(left+s+right)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
a=0
b=0
cnt=0
for i in range(N):
  if S[i]==')':
    b+=1
  else:
    a+=1
  cnt=max(cnt,b-a)
A='('*cnt+S
d=A.count(')')
e=A.count('(')
f=e-d
print(A+')'*f)

Submission status: Accepted

Solution code:

_N = int(input())
S = input()

open_parenthesis = 0
left = 0
right = 0

for s in S:
    if s == '(':
        open_parenthesis += 1
    elif s == ')':
        if open_parenthesis != 0:
            open_parenthesis -= 1
        else:
            left += 1

right = open_parenthesis

ans = '(' * left + S + ')' * right

print(ans)

Submission status: Accepted

Solution code:
def test(length, cost):
    tmp = length.replace('()', '')
    if len(length) < 2 or len(tmp) == len(length):
        return length
    return test(tmp, len(length))

n = int(input())
s = input()
last = test(s, len(s))
print(last.count(')') * '(' + s + last.count('(') * ')')

Submission status: Accepted

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

tmp1, tmp2 = s, s
tmp1 = tmp2.replace('()', '')

while not (tmp1 == tmp2):
	tmp2 = tmp1
	tmp1 = tmp2.replace('()', '')


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

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

Submission status: Accepted

Solution code:
#codng utf-8
N=int(input())
S=list(input())
s1=[0]*N#open
s2=[0]*N#close
p=[0]*N
if S[0]=='(':
    s1[0]=1
else:
    s2[0]=1
for i in range(1,N):
    if S[i]=='(':
        s1[i]=s1[i-1]+1
        s2[i]=s2[i-1]
        p[i]=p[i-1]
    else:
        s1[i]=s1[i-1]
        s2[i]=s2[i-1]+1
        if s1[i]-p[i-1]>0:
            p[i]=p[i-1]+1
        else:
            p[i]=p[i-1]
if s1[N-1]-p[N-1]>0:
    S.append(')'*(s1[N-1]-p[N-1]))
if s2[N-1]-p[N-1]>0:
    l2='('*(s2[N-1]-p[N-1])
    S.insert(0,l2)
print(''.join(S))

#print(s1,s2,p)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
S = input()
op, cl, pair = [0], [0], [0]
for i in range(N):
    if S[i] == "(":
        op.append(op[-1]+1)
        cl.append(cl[-1])
    else:
        op.append(op[-1])
        cl.append(cl[-1]+1)
for i in range(1, N+1):
    if cl[i-1] < cl[i] and op[i] - pair[-1] > 0:
        pair.append(pair[-1] + 1)
    else:
        pair.append(pair[-1])
o, c, p = op[-1], cl[-1], pair[-1]
if o - p > 0:
    S = S + ")" * (o - p)
    if c - p > 0:
        S = "(" * (c - p) + S
    print(S)
elif c - p > 0:
    S = "(" * (c - p) + S
    print(S)
else:
    print(S)

Submission status: Accepted

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

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

ans = ''
ans += '(' * list(replaced).count(')')
ans += S
ans += ')' * list(replaced).count('(')

print(ans)

Submission status: Accepted

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

rb = s.count(')')
lb = s.count('(')

r=0
l=0
ll = 0
rr = 0
for c in s:
  if c =='(' :
    l += 1
  else:
    if l > 0:
      ll += 1
    l -= 1
    if l < 0:
      l = 0          
      
for c in s[::-1]:
  if c ==')' :
    r += 1
  else:
    if r > 0:
      rr += 1
    r -= 1
    if r < 0:
      r = 0
      
print('('*(rb - rr) + s + ')'*(lb - ll))

Submission status: Accepted

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

l = 0
r = 0

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

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

Submission status: Accepted

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

l = 0
r = 0

for s in S:
    if s == '(':
        r += 1
    else:
        if r == 0:
            l += 1
        else:
            r -= 1

# print(l, r)
print('(' * l + ''.join(S) + ')' * r)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
point = 0
point2 = 0
for i in s:
    if i == "(":
        point += 1
    else:
        if point:
            point -= 1
        else:
            point2 += 1
print("("*point2+s+")"*point)

Submission status: Accepted

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

c = 0
scount = 0
for i, si in enumerate(list(s)):
  if si == '(':
    c += 1
  else:
    c -= 1
  if c < 0:
    scount += 1
    c = 0

s = '('*scount + s
s = s + ')'*c
print(s)

Submission status: Accepted

Solution code:
n=int(input())
S=input()
A=[0]*n
for i in range(n):
  if S[i]=='(':
    A[i]=1
  else:
    A[i]=-1
A=[0]+A
for i in range(1,n+1):
  A[i]=A[i]+A[i-1]
#print(A)
m=min(A)
T='('*(A[0]-m)+S+')'*(A[-1]-m)
print(T)

Submission status: Accepted

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

# 足りない（）の数を求めてみる
left = 0  # (
right = 0 # )
l_count = 0
for i in range(N):
    if S[i] == "(":
        right += 1
    elif S[i] == ")" and right > 0:
        right -= 1
    else:
        l_count += 1

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

left = "".join(["(" for _ in range(l_count)])
right = "".join([")" for _ in range(r_count)])

print(left+S+right)

Submission status: Accepted

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

from collections import defaultdict

dic = defaultdict(int)

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

top = bottom = ''
for _ in range(dic[')']):
    top += '('

for _ in range(dic['(']):
    bottom += ')'

print(top + s + bottom)

Submission status: Accepted

Solution code:
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

def SI():
    return int(readline())
def MI():
    return map(int, readline().split())
def MLI():
    return map(int, open(0).read().split())

inf = float("inf")


def main():
    N = SI()
    S = input()
    
    left = 0
    right = 0
    for s in S:
        if s == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    ret = '(' * right + S + ')' * left
    print(ret)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

L,R=0,0
l,r=0,0

for i in S:
    if i=="(":l +=1
    else:l -=1;L=min(L,l)

for i in S[::-1]:
    if i==")":r +=1
    else:r -=1;R=min(R,r)

print("("*-L+S+")"*-R)

Submission status: Accepted

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

l=0
r=0
pl=0
pr=0


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

sl=["(" for i in range(pl)]
sr=[")" for i in range(pr)]

ans=sl + S + sr

print("".join(ans))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    S = INPUT()

    l = 0
    r = 0
    for s in S:
        if s == "(":
            r += 1
        else:
            if r >= 1: 
                r -= 1
            else: 
                l += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
 
S = input()
 
l = 0
r = 0
for s in S:
  if s == "(":
    r += 1
  else:
    if r >= 1:
      r -= 1
    else:
      l += 1
print("("*l + S + ")"*r)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
S_number = []
# 変換
for i in range(N):
    if S[i] == '(':
        S_number.append(1)
    else:
        S_number.append(-1)

# print(S, S_number)
for i in range(N):
    if S_number[i] == 1:
        for j in range(i, N):
            if S_number[j] == -1:
                S_number[i] = 0
                S_number[j] = 0
                break
            if j == N-1:
                S_number[i] = 0
                S.append(')')
    # print(S, S_number)

insert_times = abs(sum(S_number))
for _ in range(insert_times):
    S.insert(0, '(')

answer = ''.join(S)
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = s
counter = 0  # 左:+1 右:-1 最終的に0にしたい
# "("の手前の"）"のインデックスでcounterが負の場合にその数ぶん左に"("を足す
# 最終的にcounterが0でない場合、その数ぶんを左右どちらかに足す

before = ""
i = 0
while i < n:
    if s[i] == "(":
        if i > 0 and before == ")":
            if counter < 0:
                t = "(" * (-counter) + t
                counter = 0
        counter += 1
        before = "("
    else:
        counter -= 1
        before = ")"
    i += 1
if counter > 0:
    t += ")" * (counter)
elif counter < 0:
    t = "(" * (-counter) + t
print(t)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
left_cnt = 0
right_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
    elif left_cnt == 0:
        right_cnt += 1
    else:
        left_cnt -= 1
#print(right_cnt, left_cnt)
print('(' * right_cnt + S + ')' * left_cnt)

Submission status: Accepted

Solution code:
def solve(n, s):
    counts = [0, 0]
    for l in s:
        if l == ')':
            if counts[0] > 0:
                counts[0] -= 1
            else:
                counts[1] += 1
        if l == '(':
            counts[0] += 1
    return '(' * counts[1] + s + ')' * counts[0]

_n = int(input())
_s = input()
print(solve(_n, _s))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    S = Scanner.string()
    c1, c2 = 0, 0
    for i in range(N):
        if S[i] == ")":
            c1 -= 1
        else:
            c1 += 1
        if S[N-i-1] == ")":
            c2 += 1
        else:
            c2 -= 1
        c1 = max(0, c1)
        c2 = max(0, c2)
    ans = "(" * c2 + S + ")" * c1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode("utf-8").rstrip()

left_cnt = 0
right_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
    elif left_cnt == 0:
        right_cnt += 1
    else:
        left_cnt -= 1

print('(' * right_cnt + S + ')' * left_cnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode("utf-8").rstrip()

res = ""
left_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
        res += '('
    elif ')' == c:
        if left_cnt > 0:
            res += ')'
            left_cnt -= 1
        else:
            res = '(' + res + ')'
if left_cnt != 0:
    res += ")" * left_cnt

print(res)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=[]
counter=0
for i in range(n):
    if s[i]=="(":
        counter+=1
    else:
        counter-=1
    l.append(counter)
suml=l[-1]
for i in range(n):
    if l[i]<0:
        s="("+s
        for j in range(n):
            l[j]+=1
        suml+=1
if suml>0:
    s+=")"*suml
print(s)

Submission status: Accepted

Solution code:
from itertools import accumulate
input()
S = input()
T = max(0, -min(accumulate(1 if s == "(" else -1 for s in S)))
U = max(0, -min(accumulate(1 if s == ")" else -1 for s in S[::-1])))
print("("*T + S + ")"*U)

Submission status: Accepted

Solution code:
from itertools import groupby

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

cnt_l = 0
cnt_r = 0
ans = ''
for key, elems in groupby(S):
    elems = list(elems)
    if key == '(':
        cnt_l += len(elems)
        ans += '(' * len(elems)
    else:
        cnt_r += len(elems)
        ans += ')' * len(elems)
        if cnt_l < cnt_r:
            ans = '(' * (cnt_r - cnt_l) + ans
            cnt_l += (cnt_r - cnt_l)

print(ans + ')' * (cnt_l - cnt_r))

Submission status: Accepted

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

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

Submission status: Accepted

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

cr = 0
cl = 0

for i in s:
  if i == "(":
    cr += 1
  else:
    if cr > 0:
      cr -= 1
    else :
      cl += 1

print("("*cl+S+")"*cr)

Submission status: Accepted

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

add_left, cash = 0, 0
for p in s:
    if cash == 0 and p == ")":
        add_left += 1
    elif p == "(":
        cash += 1
    else:
        cash -= 1

add_right, cash = 0, 0
for p in s[::-1]:
    if cash == 0 and p == "(":
        add_right += 1
    elif p == ")":
        cash += 1
    else:
        cash -= 1

print(add_left * "(" + s + add_right * ")")

Submission status: Accepted

Solution code:
N = int(input())
S = input()
A = []
a = 0
l = r = 0
for s in S:
    if s == '(':
        if a >= 0:
            a += 1
        else:
            l -= a
            a = 1
    else:
        # s == ')'
        a -= 1
if a != 0:
    if a < 0:
        l -= a
    else:
        r += a

# print(l, r)

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

Submission status: Accepted

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

t = []
num = 0
for i in range(n):
    if num == 0 and s[i] == ')':
        t.insert(0, '(')
        t.append(')')
    else:
        t.append(s[i])
        if s[i] == '(':
            num += 1
        else:
            num -= 1

if num > 0:
    for i in range(num):
        t.append(')')

for i in t:
    print(i, end='')

Submission status: Accepted

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

cr = 0
cl = 0

for i in range(N):
    if S[i] == '(':
        cr += 1
    else:
        if cr > 0:
            cr -= 1
        else:
            cl += 1
print('('*cl+S+')'*cr)