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

tmp = 0
a = 0
for i in s:
    if i == "(":
        tmp -= 1
    else:
        tmp += 1
    a = max(a, tmp)
ans = a * "(" + s
print(ans + ")" * (ans.count("(") - ans.count(")")))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = s
s += "("
cnt = 0
for i in range(n):
  if s[i] == "(":
    cnt -= 1
  else:
    cnt += 1
  if s[i] == ")" and s[i+1] == "(":
    if cnt > 0:
      t = "("*cnt + t
      cnt = 0
if cnt < 0:
  t += ")"*(-cnt)
print(t)

Submission status: Accepted

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

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:
import numpy as np
import copy

N= int(input())
S=input()
SS= copy.copy(S)
S = list(S)
#N, A, B = map(int, input().split())

flag = 1
#print(len(S))
while flag == 1:
    flag = 0
    flag2 = 1
    i = 0
    while flag2 and len(S)>1:
    # for i in range(len(S)-1):
        #print(S)
        if S[i]=="(" and S[i+1] ==")":
            # print(S, i)
            flag = 1
            del S[i] 
            del S[i]
            i -= 1
            # print(S, i)
        i += 1
        i = max(0,i)
        if i+1>=len(S):
            flag2 = 0
a=0
b=0
for i in range(len(S)):
    if S[i]=="(":
        b+=1
    elif S[i]==")":
        a+=1
#print(S)
# initialization of string to ""
A = ""
B = ""

# traverse in the string
for x in range(a):
    
    A += "("   
for x in range(b):    
    B += ")"   

        
#print(str(A)+SS+str(B))
print(A+SS+B)

Submission status: Accepted

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

while True:
    if tmp.count("()") == 0:
        break
    tmp = "".join(tmp.split("()"))

x = 0
y = 0
for c in tmp:
    if c == ")":
        x += 1
    else:
        y += 1

ans = "("*x + s + ")"*y
print(ans)

Submission status: Accepted

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

l = "("
r = ")"

t = 0
k = 0
ma = 0
for i in range(N):
  if S[i] == r:
    t += 1
  else:
    k += 1
  ma = max(ma, t - k)

A = [l] * ma + S + [r] * (ma + k - t)

print("".join(A))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
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 fractions import gcd
from bisect import bisect
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

T = S

while 1:
	if T.count("()") == 0:
		break
	try:
		T = T.replace("()", "")
	except:
		pass
l = 0
r = 0
for x in T:
	if x == ")":
		l += 1
	else:
		r += 1
print("("*l + S + ")"*r)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l, r = 0, 0
lp, rp = 0, 0

for i in range(N):
    if S[i] == '(':
        l += 1
    else:
        r += 1
    lp = max(lp, r-l)
rp = lp + l - r

ans = '(' * lp + S + ')' * rp
print(ans)

Submission status: Accepted

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

over = 0
ans_f = 0
ans_e = 0
for c in s:
    if c == "(":
        over += 1
    else:  # )
        if over > 0:
            over -= 1
        else:
            ans_f += 1

ans_e = over

ans = ("(" * ans_f) + s + (")" * ans_e)
print(ans)

Submission status: Accepted

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

over = 0
ans_f = 0
ans_e = 0
for c in s:
    if c == "(":
        over += 1
    else:  # )
        if over > 0:
            over -= 1
        else:
            ans_f += 1

ans_e = over

ans = ""
for i in range(0, ans_f):
    ans += "("

ans += s

for i in range(0, ans_e):
    ans += ")"

print(ans)

Submission status: Accepted

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

n=int(input())
s=list(input().strip())
from collections import deque
que=deque(s)
cnts=0
cntf=0
for i in range(n):
    if s[i]=="(" :
        cnts+=1
    if s[i]==")":
        if cnts==0:
            que.appendleft("(")
        else:
            cnts-=1
for i in range(cnts):
    que.append(")")
print("".join(que))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=0
l=0
r=0
a=0
for i in range(n):
  if s[i]=="(":
    a=a-1
    l=l+1
  else:
    a=a+1
    r=r+1
    if a>ans:
      ans=a
for i in range(ans):
  print("(",end="")
for i in range(n):
  print(s[i],end="")
for i in range(ans+l-r):
  print(")",end="")
print()

Submission status: Accepted

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


a=0
b=0
bb=0
for s in S:
    if s=="(":
        a+=1
    else:
        if a>0:
            a-=1
            b+=1
        else:
            bb+=1
for i in range(bb):
    S.insert(0,"(")
for i in range(a):
    S.append(")")
S="".join(S)
print(S)

Submission status: Accepted

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

Submission status: Accepted

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

L = 0
cnt = 0
for i in range(N):
    if S[i] == '(':
        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()
ans = s
flag_A = True
r = 0
l = 0
while flag_A:
    flag_B =False
    for n,i in enumerate(s):
        if n != len(s)-1 and i =="(" and s[n+1] ==")":
            s = s[:n]+s[n+2:]
            flag_B = True
            break
    if not flag_B:
        flag_A = False
for i in s:
    if i ==")":
        r += 1
    else:
        l += 1
print("("*r+ans+")"*l)

Submission status: Accepted

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

d = [0]
o = c = 0
for i in range(N):
    if S[i] == '(':
        o += 1
    else:
        c += 1
    d.append(o - c)
x = min(d)
print('(' * -x + S + ')' * (d[-1] - x))

Submission status: Accepted

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

s = "".join(["("]*r+list(s)+[")"]*l)
  
print(s)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
# import sys
# input = sys.stdin.readline

N=one_int()
S=one_str()

head = 0
tail = 0

point=0
for a in S:
    if a =="(":
        point+=1
    else:
        point -=1
    if point<0:
        head += 1
        
        #ここで先頭にカッコをつけるのでその分のポイントは差し引き０
        point += 1


print("("*head + S + abs(point)*")")

Submission status: Accepted

Solution code:
n=int(input())
s=input()
if s[0]=="(":
    c=1
    d=1
else:
    c=-1
    d=-1
for i in range(1,n):
    if s[i]=="(":
        d+=1
    else:
        d-=1
        c=min(c,d)
if c<0:
    s="("*(-c)+s
print(s+")"*(s.count("(")-s.count(")")))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
tmp = S[-1]
index = 0
ans = ''
cnt1 = 0
cnt2 = 0
for i in range(N):
    if S[i] == '(':
        cnt1 += 1
    elif cnt1 == 0:
        cnt2 += 1
    else:
        cnt1 -= 1

print('(' * cnt2 + S + ')' * cnt1)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
validation = [False for _ in range(n)]

r = 0
l = 0
for i in range(n):
    if "(" == s[i]:
        r += 1
    else:
        if r > 0:
            r -= 1
        else:
            l += 1
print("(" * l + "".join(s) + ")" * r)

Submission status: Accepted

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

ans=''
b=0
for c in reversed(S):
    if c==')':
        b+=1
        ans=c+ans
    else:
        if b==0:
            ans=c+ans
            ans+=')'
        else:
            b-=1
            ans=c+ans
for _ in range(b):
    ans='('+ans
print(ans)

Submission status: Accepted

Solution code:


if __name__ == '__main__':
    N=int(input())
    S=input()
    r=0
    l=0

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()

# それぞれ必要な数を確認
lneed = cnt = 0
for s in S:
    if s == ')':
        cnt += 1
        lneed = max(lneed, cnt)
    else:
        cnt -= 1
rneed = cnt = 0
for s in S[::-1]:
    if s == '(':
        cnt += 1
        rneed = max(rneed, cnt)
    else:
        cnt -= 1

# 辞書順最小なので、(は全部左に、)は全部右に付ける
ans = ('(' * lneed) + S + (')' * rneed)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
t=s
l=str()
r=str()
while '()' in t:
  t=t.replace('()','')
if len(t)==0:
  print(s)
else:
  for i in range(len(t)):
    if t[i]=='(':
      r+=')'
    else:
      l+='('
  print(l+s+r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input().strip())
s = input().strip()
cnt = 0
pre = ''
for ss in s:
    if ss == '(':
        cnt += 1
    elif ss == ')':
        cnt -= 1
        if cnt < 0:
            pre += '('
            cnt += 1
else:
    post = ')' * cnt
print(pre + s + post)

Submission status: Accepted

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

    if i == N-1:
        d = cnt

S = "("*(-x) + S + ")"*(d+(-x))
print(S)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
s = input()
cnt = [0]
ans = deque(list(s))
for i in range(n):
  if s[i]=="(":
    cnt.append(cnt[-1]+1)
  else:
    cnt.append(cnt[-1]-1)
rt = min(cnt)
if rt<0:
  ans.extendleft("("*(-rt))
if cnt[-1]-rt>0:
  ans.extend(")"*(cnt[-1]-rt))
print(*ans,sep="")

Submission status: Accepted

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

A1, A2 = [0 for _ in range(N)], [0 for _ in range(N)]
for i, s in enumerate(S):
  if i == 0:
    if s == '(': A1[i] = 1
    else: A2[i] = 1
  else:
    if s == '(':
      A1[i] = A1[i-1] + 1
      A2[i] = A2[i-1] 
    else:
      A1[i] = A1[i-1] 
      A2[i] = A2[i-1] + 1

A3, A4 = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N-1, -1, -1):
  if i == N-1:
    if S[i] == '(': A3[i] = 1
    else: A4[i] = 1
  else:
    if S[i] == '(':
      A3[i] = A3[i+1] + 1
      A4[i] = A4[i+1] 
    else:
      A3[i] = A3[i+1] 
      A4[i] = A4[i+1] + 1

v1 = max(max([a2-a1 for a1, a2 in zip(A1,A2)]),0)
v2 = max(max([a3-a4 for a3, a4 in zip(A3,A4)]),0)
print('('*v1+S+')'*v2)

Submission status: Accepted

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

def main():
  left=0
  right=0
  for char in s:
    if char=="(":
      right+=1
    else:#")"
      if right>0:
        right-=1
      else:
        left+=1
  return (left,right)
      

l,r=main()
print("("*l+s+r*")")

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
s = sys.stdin.readline().rstrip()

def main():
    l = r = 0
    for char in s:
        if char == '(':
            r += 1
        elif char == ')':
            if r:
                r -= 1
            else:
                l += 1

    return '(' * l + s + ')' * r

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
# まず始めカッコの数を確定させる
N = int(input())
S = input()

hazimekakko = 0
owarikakko = 0
sa = -1
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
    sa = max(sa, owarikakko-hazimekakko)

S = sa*"(" + S

hazimekakko = 0
owarikakko = 0
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
print(S + ")"*(hazimekakko-owarikakko))

Submission status: Accepted

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

    left = 0
    right = 0
    t = 0
    for c in list(S):
        if c == '(':
            t += 1
        if c == ')':
            if t > 0:
                t -= 1
            else:
                left += 1
    right = t
    print('(' * left + S + right * ')')


m()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
c, d = 0, 0
for i in range(N):
  if S[i] == '(':
    c += 1
  elif S[i] == ')' and c > 0:
    c -= 1
  if S[N-i-1] == ')':
    d += 1
  elif S[N-i-1] == '(' and d > 0:
    d -= 1
print(d*'(' + S[:] + c*')')

Submission status: Accepted

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

right = 0
p = 0
left = 0
for s in sl:
    if s == "(":
        p -= 1
    else:
        p += 1
        left += 1
        right = max(p, right)

x = right + n - 2*left
print("("*right + ss + ")"*x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=int(input())
    s=input()
    now=0
    l=0
    for c in s:
        if c=="(":
            now+=1
        else:
            now-=1
        if now==-1:
            l+=1
            now=0
    ans="("*l+s+")"*now
    print(ans)
main()

Submission status: Accepted

Solution code:
# 始めカッコの個数を先に確定させる
# ある特定の時点で")"の方が多いなら、あとから"("が出て来ても遅い
ans = 0  # これの最小値になった絶対値分を文頭につける
N = int(input())
S = input()
hazimekakko = 0
owarikakko = 0
for i in range(N):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
    ans = max(ans, owarikakko-hazimekakko)
# 終わりかっこの方が多いタイミングのその量を確定させる
S = abs(ans)*"(" + S

hazimekakko = 0
owarikakko = 0
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1

S = S + (hazimekakko-owarikakko)*")"
print(S)

Submission status: Accepted

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

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

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

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

print(z)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
a=[0]
for c in S:
    a.append(a[-1]+(1 if c=='(' else -1))
k=-min(a)
l=S.count('(')+k-S.count(')')
ans='('*k+S+')'*l

print(ans)

Submission status: Accepted

Solution code:
# ABC146 D - Insertion
n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    # ss=ss.replace('()','')
    while ss.count('()')>0:
        ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s

    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
c1 = 0
c2 = 0
c = 0
for i in s:
    if i == '(':
        c1 += 1
    else:
        c2 += 1
        if c1+c< c2:
            c += 1
print('('*c + s + ')'*(c+c1-c2))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
s = input()
stack = []
a = 0
b = 0
for i in range(N):
  if stack and stack[-1] == "(" and s[i] == ")":
    stack.pop()
    a -= 1
  else:
    stack.append(s[i])
    if s[i] == "(":
      a += 1
    else:
      b += 1

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
unpaired_open, unpaired_close = 0, 0
for c in S:
    if c=='(': unpaired_open+=1
    elif unpaired_open==0: unpaired_close += 1
    else: unpaired_open -=1

print('('*unpaired_close + S + ')'*unpaired_open)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
s=input()
c=0
mm=0
for i in s:
    if i=='(':
        c+=1
    else:
        c-=1
    mm=min(mm,c)

print('('*-mm+s+')'*(c-mm))

Submission status: Accepted

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

q = deque()
for s in arg:
    if len(q) == 0:
        q.append(s)
    else:
        if q[-1] == '(' and s == ')':
            q.pop()
        else:
            q.append(s)
l = 0
r = 0
for i in range(len(q)):
    st = q.pop()
    if st == '(':
        r += 1
    else:
        l += 1
print('(' * l + arg + ')' * r)

Submission status: Accepted

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

count = 0
for i in s:
    if i == ")":
        count += 1
    else:
        s = "(" * count + s
        if count > 0:
            count = -1
        else:
            count -= 1

if count > 0:
    s = "(" * count + s
elif count < 0:
    s = s + ")" * -count

print(s)

Submission status: Accepted

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

#このパターンはスタックで管理していくと良い(()の整合性取れているか)
#湖の問題も整合性取れるかで判断

#"("がプラスで")"がマイナス
#全部0以上にする(最小をプラスする)
c=0
m=0
for i in s:
    if i==")":
        c-=1
    else:
        c+=1
    m=min(m,c)
s=abs(m)*"("+s
l=s.count("(")
k=s.count(")")
#print(m)
if k-l>0:
    print((k-l)*"("+s)
else:
    print(s+(l-k)*")")

Submission status: Accepted

Solution code:
N = int(input())
S = input()
tmp = ""
for letter in S:
    if tmp == "":
        tmp += letter
    elif letter == ")" and tmp[-1] == "(":
        tmp = tmp[:-1]
    else:
        tmp += letter

head = "(" * tmp.count(")")
tail = ")" * tmp.count("(")
print(head + S + tail)

Submission status: Accepted

Solution code:
# D - Insertion

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

s = S
for _ in range(50):
    s = s.replace("()", "")

ans = "(" * s.count(")") + S + ")" * s.count("(")
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
s = input()
cnt = 0
_max = 0
for _s in s[::-1]:
    if _s == ")":
        cnt -= 1
    else:
        cnt += 1
    _max = max(cnt, _max)
s += ")" * _max

cnt = 0
_max = 0
for _s in s:
    if _s == "(":
        cnt -= 1
    else:
        cnt += 1
    _max = max(cnt, _max)
s = "(" * _max + s
ct = Counter(s)

if ct.get("(") is None:
    ct["("] = 0
if ct.get(")") is None:
    ct[")"] = 0
if ct[")"] > ct["("]:
    s = "(" * (ct[")"] - ct["("]) + s
else:
    s = s + ")" * (ct["("] - ct[")"])
print(s)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cnt1=0
for i in range(n):
    if s[i]=="(":
        cnt1+=1
    else:
        if cnt1>0:
            cnt1-=1
        else:
            pass

cnt2=0
for i in range(n-1,-1,-1):
    if s[i]==")":
        cnt2+=1
    else:
        if cnt2>0:
            cnt2-=1
        else:
            pass

print(cnt2*"("+s+cnt1*")")

Submission status: Accepted

Solution code:
# D - Insertion

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

s = S
for _ in range(50):
    s = s.replace("()", "")

ans = "(" * s.count(")") + S + ")" * s.count("(")
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ary = []
if S[0] == '(':
    ary.append(1)
else:
    ary.append(0)
    ary.append(1)
for i in range(1, N):
    if S[i-1] == S[i]:
        ary[-1] += 1
    else:
        ary.append(1)
if len(ary) % 2:
    ary.append(0)
c = [0, 0]
for i in range(0, len(ary), 2):
    c[0] += ary[i]
    c[1] += ary[i+1]
    if c[0] < c[1]:
        ary[0] += c[1]-c[0]
        c[0] = c[1]
if c[0] > c[1]:
    ary[-1] += c[0]-c[1]
ans = ''
for i, n in enumerate(ary):
    if i % 2 == 0:
        ans += '('*n
    else:
        ans += ')'*n
print(ans)

Submission status: Accepted

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


def solve(N: int, S: str):
    stack = []
    for i in range(N):
        if not stack:
            stack.append(S[i])
            continue

        if S[i] == "(":
            stack.append(S[i])
        else: ## )
            if stack[-1] == "(":
                stack.pop()
            else:
                stack.append(S[i])
    right_count = stack.count('(')
    left_count = stack.count(')')

    answer = '('*left_count+S+')'*right_count
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
s = 0
mi = 0
for i in range(N):
    s += 1 if S[i] == "(" else -1
    mi = min(mi, s)
if s > 0:
    print(-mi * "(" + S + ")" * (s-mi))
else:
    print("(" * max(-s, -mi) + S + ")" * (max(-s, -mi) + s))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
sl=list(S)
change=[0]
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
r_add=0
l_add=0
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    continue
  elif r>l:
    if r_add>0:
      if r_add>=r-l:
        r_add-=r-l
      else:
        l_add+=r-l-r_add
        r_add=0
        
    else:
      l_add+=r-l
      
  else:
    r_add+=l-r
      
print('('*l_add+S+')'*r_add)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
stack = []
for i in S:
    if len(stack) == 0:
        stack.append(i)
    else:
        prev = stack.pop()
        if prev == "(" and i == ")":
            continue
        else:
            stack.append(prev)
            stack.append(i)
ans = S
for i in stack:
    if i == ")":
        ans = "(" + ans
    else:
        ans = ans + ")"
print(ans)

Submission status: Accepted

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

a = []
tmp = 0
for i in range(n):
    if s[i] == '(':
        tmp += 1
    else:
        tmp -= 1
    a.append(tmp)

m = min(a)
if m < 0:
    ans = -m * '(' + s
    last = -m + a[-1]
else:
    ans = s
    last = a[-1]
if last > 0:
    ans += ')' * last
print(ans)

Submission status: Accepted

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

m = 0
min_m = 0

for c in S:
    if c == '(':
        m += 1
    else:
        m -= 1
    min_m = min(min_m, m)

ans = '('*(-min_m) + S + ')'*(m-min_m)
print(ans)

Submission status: Accepted

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

    left = 0
    right = 0
    for s in S:
        if s == '(':
            right += 1
        else:
            if right <= 0:
                left += 1
            else:
                right -= 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g
 
def main():
    n=inp()
    s=input()
    r,l=0,0
    ans=[]
    for i in range(n):
        if s[i]=='(':
            r+=1
        elif s[i]==')':
            if r==0:
                l+=1
            else:
                r-=1
    for i in range(l):
        ans.append('(')
    for i in range(n):
        ans.append(s[i])
    for i in range(r):
        ans.append(')')
    print(''.join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    left = 0
    right = 0
    stack = []
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                left += 1
    right = len(stack)
    print("("*left + S + ")"*right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
s = input()
lCnt = 0
rCnt = 0
stack = deque()
stack.append(s[0])

for i in range(1, len(s)):
#for i in range(0, len(s)):
    if len(stack) == 0:
        stack.append(s[i])
        continue

    prev = stack.pop()

    if prev == '(' and s[i] == ')':
        continue
    else:
        stack.append(prev)
        stack.append(s[i])

#print(stack)

for i in range(len(stack)):
    if stack[i] == '(':
        lCnt += 1
    else:
        rCnt += 1

s += ')' * lCnt
s = '(' * rCnt + s

print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    S=input()
    a=0
    b=0

    for i in range(n):
        if(S[i]=='('):
            a+=1
        else:
            if(a>0): a-=1
            else: b+=1
    P='('*b

    a=0
    b=0
    for i in range(n-1,-1,-1):
        if(S[i]==')'):
            a+=1
        else:
            if(a>0): a-=1
            else: b+=1
    Q=')'*b
    print(P+S+Q)
resolve()

Submission status: Accepted

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

c1 = 0 #"("の数
c2 = 0 #")"の数

for i in range(N-1, -1, -1):
    if S[i] == "(":
        c1 += 1
    else:
        c2 += 1
    if c1 > c2:
        S.append(")")
        c2 += 1
        
if c2 > c1:
    T = ["("]*(c2-c1)
    S = T + S
    
print("".join(S))

Submission status: Accepted

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

#入力
N = input()
S = input()

if S[0] == ")" :
  S = "(" + S
if S[-1] == "(" :
  S = S + ")"

r = S.count("(")
l = S.count(")")

if r < l :
  for i in range(l-r) :
    S = "(" + S
elif r > l :
  for i in range(r-l) :
    S = S + ")"

nowS = S
endflag = 0
while endflag == 0 :
  S = nowS
  while (len(S) != 0) :
    S = S.replace("()", "")
    if "()" not in S :
      break
    
  if len(S) == 0 :
    print (nowS)
    endflag = 1
  else :
    nowS = "(" + nowS + ")"

Submission status: Accepted

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            right += 1 
            # これ以前に出現している')'の数が'('の数より多い可能せがあるのでleftを削ることはできないため、ペアになる可能性としての')'を追加
        elif char == ')':
            if right: 
                # rightがあるならこれより前に必ずペア未確定の'('が存在するのでrightの可能性を一つ削ってこれを代わりにその'('とペアにする
                right -= 1
            else: 
                # rightがない場合はペア未確定の'('がこれ以前に出現していないということので'('を追加してこれとペアにするしかない
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()