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:
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 
            # prefixが')'の可能性があるのでleftを削ることはできない
        elif char == ')':
            if right: 
                # rightがあるならこれより前に必ず'('が存在するのでrightの可能性を一つ削ってこれを代わりにその'('とペアにする
                right -= 1
            else: # rightがない場合はこれとペアになることのできる'('がこれ以前に出現していないということので追加
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()

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 == '(':
            # if left:
            #     left -= 1
            # else:
                right += 1
        elif char == ')':
            if right:
                right -= 1
            else:
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)

            

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def l(s):
    return s.count("(")

def r(s):
    return s.count(")")

prev = ""
while prev != s:
    prev = s
    pt = 0
    while True:
        #print(pt)
        if pt>=len(s):
            break
        char = s[pt]
        #print("  ".join([s[:pt],char, s[pt+1:]]))
        if char=="(" and l(s[pt+1:]) >= r(s[pt+1:]):
            s = s+")"
        if char==")" and l(s[:pt]) <= r(s[:pt]):
            s = "("+s
            pt+=1
        pt+=1

print(s)

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:
n=int(input())
S=input()

l,cnt1=0,0
for s in S:
  if s=='(':
    cnt1+=1
  else:
    cnt1-=1
    l=min(l,cnt1)
r,cnt2=0,0
for s in S[::-1]:
  if s==')':
    cnt2+=1
  else:
    cnt2-=1
    r=min(r,cnt2)
print('('*-l+ S + ')'*-r)

Submission status: Accepted

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

l,cnt1=0,0
for s in S:
  if s=='(':
    cnt1+=1
  else:
    cnt1-=1
    l=min(l,cnt1)
r,cnt2=0,0
for s in S[::-1]:
  if s==')':
    cnt2+=1
  else:
    cnt2-=1
    r=min(r,cnt2)
print('('*-l+ S + ')'*-r)

Submission status: Accepted

Solution code:
n=int(input())
S=input()
ans=S
stack=[]
for i in range(len(S)):
  if S[i]=="(":
    stack.append("(")
  else:
    if len(stack)==0:
      ans="("+ans
    else:
      stack.pop()
ans+=")"*len(stack)

print(ans)

Submission status: Accepted

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

stack = []
for c in s:
  #抜き出したもの(c)が左括弧だった場合
  if c == "(":
    stack.append(c)
    
  #抜き出したもの(c)が右括弧だった場合
  else:
    #stackがなかった場合
    if not stack:
      d.appendleft('(')
      
    #stackがあった場合
    else:
      #末尾をstackから削除する
      stack.pop()

#まだstackが残っていたらそれは左かっこなので、その数だけ ")" を足す
while stack:
  stack.pop()
  d.append(')')
  
print("".join(list(d)))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
S = list(input())
S2 = np.array([1 if x == ')' else -1 for x in S])
S_cum = S2.cumsum()
S = ['('] * S_cum.max() + S
left = S.count('(')
right = len(S) - left
if left > right:
    S = S + [')'] * (left-right)
elif right > left:
    S = ['('] * (right-left)
print(''.join(S))

Submission status: Accepted

Solution code:
def examD():
    N = I()
    St = S()
    cur = 0
    left = 0; right = 0
    for s in St:
        if s=="(":
            cur +=1
        if s==")":
            if cur>0:
                cur -=1
            else:
                left +=1
    right = cur
    ans = "("*left + St + ")"*right
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

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

r = 0
l = 0
for i in range(n):
    if r <= 0:
        if s[i] == ')':
            l += 1
        else:
            r += 1
    else:
        if s[i] == ')':
            r -= 1
        else:
            r += 1
result = '('*abs(l) + s + ')'*abs(r)

print(result)

Submission status: Accepted

Solution code:
#insertion
n=int(input())
s=input()
count=1
Llist=[]
Rlist=[]
s=s+"X"
for i  in range(n):
    if s[i]==s[i+1]:
        count+=1
    else:
        if s[i]=="(":
            Llist.append(count)
        else:
            Rlist.append(count)
        count=1
#LのがRよりもつよい
if s[0]==")":
    Llist.insert(0,0)
if s[-2]=="(":
    Rlist.append(0)

Lsum=0
Rsum=0
for i in range(len(Llist)):
    Lsum+=Llist[i]
    Rsum+=Rlist[i]
    if Lsum>=Rsum:
        pass
    elif Lsum<Rsum:
        Llist[0]+=(Rsum-Lsum)
        Lsum+=(Rsum-Lsum)
if Lsum!=Rsum:
    Rlist[-1]+=(Lsum-Rsum)
anstr=""
for i in range(len(Llist)):
    a,b=Llist[i],Rlist[i]
    anstr+="("*a
    anstr+=")"*b
print(anstr)

Submission status: Accepted

Solution code:

a=int(input())
b=input()
s1=s2=e1=e2=0
str1=str2=''

for i in range(len(b)):
    if( b[i] == '(' ):
        s1-=1
    elif( b[i] == ')' ):
        s1+=1
        if(s1>s2):
            s2=s1
            str1+='('

for i in range(len(b)-1,-1,-1):
    if( b[i] == '(' ):
        e1+=1
        if(e1>e2):
            e2=e1
            str2+=')'
    elif( b[i] == ')' ):
        e1-=1

print(str1 + b + str2)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = list(str(input().rstrip('\n')))
    s = collections.deque(s)
    ds = collections.deque(s)
    while s:
        while True:
            ll = len(s)
            s = collections.deque(list("".join(s).replace("()", "")))
            if ll == len(s):
                break
        if len(s) != 0:
            if s[0] == "(":
                s.append(")")
                ds.append(")")
            else:
                s.appendleft("(")
                ds.appendleft("(")
        else:
            print("".join(ds))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#挿入
#辞書順最少,左端に"("寄せる

from collections import deque

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

ans = deque()
cnt = 0
for i in range(n):
    if s[i]==")":
        if cnt<=0:
            ans.appendleft("(")
            ans.append(")")
        else:
            ans.append(")")
            cnt -= 1
    else:
        ans.append("(")
        cnt += 1
for i in range(cnt):
    ans.append(")")

print(''.join(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

open_ = 0  # (
close_ = 0  # )

ans = deque(s)
for c in s:
    if c == '(':
        open_ += 1
    else:
        close_ += 1
        if close_ > open_:
            ans.appendleft('(')
            close_ -= 1
for _ in range(close_ - open_):
    ans.appendleft('(')
for _ in range(open_ - close_):
    ans.append(')')
print(*ans, sep='')

Submission status: Accepted

Solution code:
n=int(input())
s=input()
data=[0]*n
for i in range(n):
    if s[i]=="(":
        data[i]=1
    else:
        data[i]=-1
for i in range(1,n):
    data[i]+=data[i-1]
k=data[-1]
l=min(data)
if l<0:
    l*=-1
    k+=l
    if k>=0:
        print("("*l+s+")"*k)
    else:
        print("("*(l-k)+s)
else:
    if k>=0:
        print(s+")"*k)
    else:
        print("("*(-k)+s)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
r = [i for i in range(n) if s[i] == "("]
l = [i for i in range(n) if s[i] == ")"]
if r == []: print(n*"(" + s)
elif l == []: print(s + n*")")
elif min(r) > max(l):
    print(len(l)*"(" + s + len(r)*")")
else:
    cnt = 0
    for i in reversed(range(len(r))):
        if r[i] < max(l):
            cnt += 1
            l.pop(-1)
        if l == []: break
    print((len(l)) * "(" + s + (len(r) - cnt) * ")")

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
mS=[i for i in S]

j=1
while j==1:
  j=0
  for i in reversed(range(len(S)-1)):
    if S[i]=="(" and S[i+1]==")":
      S.pop(i+1)
      S.pop(i)
      j=1
      break

print("".join(["("]*S.count(")")+mS+[")"]*S.count("(")))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
x = 0
s = set()
for i in range(N):
  if S[i] == "(": x += 1
  else: continue
  for j in range(i, N):
    if j in s:
      continue
    if S[j] == ")":
      x -= 1
      s.add(j)
      break
y = 0
for i in range(N - 1, -1, -1):
  if S[i] == ")":
    if i in s: continue
    y += 1
  else: continue
#print(x, y)
if x > 0:
  S += [")"] * x
if y > 0:
  S = ["("] * y + S
print("".join(S))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
L,R=0,0

for i in S:
    if i=='(':
        R+=1
    else:
        if R:  #0でさえなければTrue扱い
            R-=1
        else:
            L+=1

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

Submission status: Accepted

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

Submission status: Accepted

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

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

if d[-1] < 0:
    d = [i for i in range(1, abs(d[-1]) + 1)] + [x - d[-1] for x in d]
m = min(d)
if m < 0:
    d = [i for i in range(1, abs(m) + 1)] + [x - m for x in d]
if d[-1] > 0:
    d = d + [i for i in reversed(range(d[-1]))]

ans = ''
for i, num in enumerate(d):
    if i == 0:
        ans += '('
    elif d[i] > d[i - 1]:
        ans += '('
    else:
        ans += ')'
print(ans)

Submission status: Accepted

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

for s in S:
    if stack:
        p = stack.pop()
        if p == "(" and s == ")":
            continue
        else:
            stack.append(p)
            stack.append(s)
    else:
        stack.append(s)

while stack:
    p = stack.pop()
    if p == "(":
        S = S + ")"
    else:
        S = "(" + S

print(S)

Submission status: Accepted

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

for i in range(n):
    if s[i]==')':
        s[i]=1
    else:
        s[i]=-1

ans=0
v=[]
for i in range(n):
    ans+=s[i]
    if ans>0:
        v.append(-1)
        ans-=1
s=v+s
if ans<0:
    for i in range(abs(ans)):
        s.append(1)
for i in range(len(s)):
    if s[i]==-1:
        s[i]='('
    else:
        s[i]=')'
print(''.join(s))

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = list(str(input().rstrip('\n')))
    s1 = collections.deque(s)
    s2 = collections.deque(s)
    while True:
        ln = len(s1)
        while True:
            s1 = collections.deque(list("".join(s1).replace("()", "")))
            if len(s1) == ln:
                break
            else:
                ln = len(s1)
        if len(s1) == 0:
            break
        elif s1[0] == "(":
            s1.append(")")
            s2.append(")")
        else:
            s1.appendleft("(")
            s2.appendleft("(")
    print("".join(s2))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
global data
data = [[0 for i in range(n)] for j in range(2)]

for i in range(n):
    data[0][i] = s[i]
    #data[i][1]はペアがいるかどうかの判定
    data[1][i] = 0
#左向きに探していく
#ペアが見つからなければ挿入する。
def Lsearch(index):
    while index >= 0:
        if data[0][index] == '(' and data[1][index] == 0:
            data[1][index] = 1
            return False
        index -= 1
    return True
#右向きに探しに行く
def Rsearch(index):
    if index >= len(data[0]):
        data[0].insert(len(data[0]), ')')
        data[1].insert(len(data[0]), 1)
        return
    elif data[0][index] == ')' and data[1][index] == 0:
        data[1][index] = 1
    else:
        Rsearch(index + 1)
i = 0
while i < len(data[0]):
    #print(data[1])
    #相手が見つかっていれば終わり
    # ) で、相手が見つかっていなければ左側を探す
    if data[0][i] == ')' and data[1][i] == 0:
        if Lsearch(i - 1):
            data[1][i] = 1
            data[0].insert(0, '(')
            data[1].insert(0, 1)
    # ( で、相手が見つかっていなければ、右側を探す
    elif data[0][i] == '(' and data[1][i] == 0:
        Rsearch(i + 1)
        data[1][i] = 1
    i += 1
print("".join(data[0]))
#再帰の書き方はたぶんあってるはずだが、なぜかindexが184やら311やらに初期化されてしまう

Submission status: Accepted

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

N = int(input().split()[0])
S = input()

ext_n_open, ext_n_close = 0, 0
sub_s = ""

for i, ch in enumerate(list(S)):
    if ch == "(":
        ext_n_open += 1
    else:
        if ext_n_open == 0:
            # 余分な)である
            ext_n_close += 1
        else:
            # 以前出た(と相殺
            ext_n_open -= 1

ans = "(" * ext_n_close + S + ")" * ext_n_open

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
s = input()
acc = [0] * n
L = ''
for i in range(n):
    if i == 0:
        if s[i] == '(':
            acc[i] = 1
        else:
            acc[i] = -1
    else:
        if s[i] == '(':
            acc[i] = acc[i-1] + 1
        else:
            acc[i] = acc[i-1] - 1
x = min(acc)
if x < 0:
    L += '(' * abs(x) + s + ')' * (acc[-1] - x)
else:
    L += s + ')' * acc[-1]
print(L)

Submission status: Accepted

Solution code:
n=int(input())
w=input()
l=0
r=0
m=0
for i in range(n):
  if w[i]=="(":
    l+=1
  else:
    r+=1
  m=max(m,r-l)
if m==0:
  if l>r:
    print(w+")"*(l-r))
  else:
    print("("*(r-l)+w)
else:
  if l>r:
    print("("*m+w+")"*(m+l-r))
  else:
    if l+m>r:
      print("("*m+w+")"*(-r+l+m))
    elif l+m==r:
      print("("*m+w)
    else:
      print("("*(r-l-m)+w)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
stk=[]
cnt=0 
add=0
for i in s:
    if i=='(':
        stk.append(i)
    else:
        if not stk:
            cnt+=1 
        else:
            stk.pop()
add=len(stk)
print('('*cnt+s+')'*add)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l,r = 0,0
ans = ''

for i in s:
    ans += i
    if i=='(':
        l += 1
    else:
        r += 1
    if l-r<0:
        ans = '(' + ans
        l += 1

diff = l-r
ans += ')' * diff
print(ans)

Submission status: Accepted

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

# ( と )　の数を数える。差の分だけ (→左から追加。 )→右から追加
l=0
r=0
ans = ""

for i in s:
  ans += i
  if i == "(":
    l += 1
  else:
    r += 1
  
  if l - r < 0:
    ans = "(" + ans
    l += 1
    
diff = l - r
ans += ")" * diff
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
stack = []
l = 0
r = 0
for i in range(N):
    if S[i] == "(":
        stack.append(1)
    elif S[i] == ")":
        if not stack:
            l += 1
        else:
            stack.pop()

r = len(stack)
print(l*"(" + S + r*")")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
S = list(input())
stack = deque()
ans = ""
for s in S:
  ans += s
  if s == "(":
    stack.append(s)
  else:
    if not stack:
      ans = "("+ans
    else:
      _ = stack.pop()
if stack:
  ans += ")"*len(stack)
print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    t = s
    while True:
        l_len = len(s)
        while True:
            s = s.replace("()", "")
            if len(s) == l_len:
                break
            else:
                l_len = len(s)
        if len(s) == 0:
            print(t)
            exit()
        else:
            if s[0] == ")":
                s = "".join((list("(") + list(s)))
                t = "".join((list("(") + list(t)))
            else:
                s = "".join((list(s)) + list(")"))
                t = "".join((list(t)) + list(")"))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
A = [0 for _ in range(N+1)]
for i in range(N):
    if S[i]=="(":
        A[i+1] = A[i]+1
    else:
        A[i+1] = A[i]-1
amin = min(A)
a = A[-1]
if amin>=0:
    x = S+")"*a
else:
    x = "("*abs(amin)+S
    a += abs(amin)
    x = x+")"*a
print(x)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
a,t=0,0
for i in S:
    if i==")":
        t+=1
        a=max(a,t)
    else:
        t-=1
b,t=0,0
for i in range(N-1,-1,-1):
    if S[i]=="(":
        t+=1
        b=max(b,t)
    else:
        t-=1
print("("*a,end="")
print(S,end="")
print(")"*b,end="")

Submission status: Accepted

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

lcount = 0
rcount = 0

count = 0
for i in range(n):
  if s[i] == ')':
    count += 1
  else:
    count -= 1
  lcount = max(lcount,count)

count = 0
for i in reversed(range(n)):
  if s[i] == '(':
    count += 1
  else:
    count -= 1
  rcount = max(rcount,count)
  
print('('*lcount+s+')'*rcount)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import deque

def main():
    n = int(input().strip())
    S = input().strip()
    s = deque(S)
    st = []
    for c in S:
        if c == ')':
            if len(st) == 0:
                s.appendleft('(')
            else:
                st.pop()
        else:
            st.append('(')
    s.append(')' * len(st))
    print(''.join(s))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans += S + ')' * cnt
print(ans)

Submission status: Accepted

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

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

result = "(" * rest_right_parenthesis + s + ")" * rest_left_parenthesis
print(result)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
cnt = 0
revS = []
for s in reversed(S):
    revS.append(s)
for s in S:
    if s == "(":
        cnt += 1
    else:
        if cnt <= 0:
            print("(", end="")
        if cnt > 0:
            cnt -= 1
print(S,end="")
cnt = 0
for s in revS:
    if s == ")":
        cnt += 1
    else:
        if cnt <= 0:
            print(")", end="")
        if cnt > 0:
            cnt -= 1

Submission status: Accepted

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

    l_count = 0
    r_count = 0
    shift = 0
    for i in range(len(S)):
        if S[i + shift] == '(':
            l_count += 1
        else:
            r_count += 1

        if r_count > l_count:
            S = '(' + S
            l_count += 1
            shift += 1

    if l_count > r_count:
        n = l_count - r_count
        S = S + ')' * n

    print(S)

Submission status: Accepted

Solution code:
#64d
import re

N = int(input()) #N<100
S = str(input()) #|S|=N

inputS = S

#()を打ち消す。
for _ in range(50): #whileは遅いのでforで。
    if "()" in S:
        S = S.replace("()","").strip()
    else:
        break
        
#print(S)
#print(inputS)

#挿入文字列は残ったものを反転したもの
insertS = S.translate(str.maketrans({'(': ')', ')': '('}))
#print(insertS)

ans = inputS.split()

#(は最左端に)は最右端に入れればOK
for insert_bracket in insertS:
    if insert_bracket == "(":
        ans.insert(0,"(")
    else:
        ans.append(")")
        
print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = S()
kakko = ["(", ")"]

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

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

print(kakko[0]*left + s + kakko[1]*right)

Submission status: Accepted

Solution code:
import itertools
import math
N = int(input())
S = input()
cot = 0
left_count = 0
for c in S:
    if c == ")":
        if cot > 0:
            cot -=1
        else:
            left_count += 1
    else:
        cot += 1
print("(" * left_count + S + cot * ")")

Submission status: Accepted

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


def solve(N: int, S: str):
    from collections import deque
    d = deque(list(S))
    st = 0
    ad = deque()

    while(len(d)):
        t = d.pop()
        if t == ')':
            ad.appendleft(t)
            st += 1
        else:
            if(st > 0):
                st -= 1
            else:
                ad.append(')')

            ad.appendleft('(')
                    
    ad.appendleft('(' * st)
        
    print(''.join(ad))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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()
max1 = 0
cnt1 = 0
for c in s:
    cnt1 += 1 if c == ')' else - 1
    max1 = max(max1, cnt1)
s = '(' * max1 + s

max2 = 0
cnt2 = 0
for c in reversed(s):
    cnt2 += 1 if c == '(' else - 1
    max2 = max(max2, cnt2)
s = s + ')' * max2

print(s)

Submission status: Accepted

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

left_max = 0
tmp = 0
for i in range(n):
    if s[i] == ')':
        tmp += 1
    else:
        tmp -= 1
    left_max = max(left_max, tmp)

right_max = 0
tmp = 0
for i in range(n):
    if s[::-1][i] == '(':
        tmp += 1
    else:
        tmp -= 1
    right_max = max(right_max, tmp)

for i in range(left_max):
    s = '(' + s
for i in range(right_max):
    s = s + ')'
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

L=0
R=0

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(R):
        S.append(")")

for i in range(L):
    S.insert(0,"(")
    
print("".join(S))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    s = input()
    l, r = 0, 0
    for c in s:
        if c == "(":
            l += 1
        elif l > 0 and c == ")":
            l -= 1
    for c in s[::-1]:
        if c == ")":
            r += 1
        elif r > 0 and c == "(":
            r -= 1
    ans = "(" * r + s + ")" * l
    print(ans)


if __name__ == "__main__":
    resolve()

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

temp=list(S)
f=True

while f :
    f=False
    L=len(temp)
    for i in range(L-2,-1,-1):
        if  "".join(temp[i:i+2])=="()":
            temp.pop(i+1)
            temp.pop(i)
            f=True

Ltemp=len(temp)
if Ltemp==0:
    print(S)
    exit()
    
if temp[0]=="(":
    add=")"*len(temp)
    ans=S+add
else:
    cnt1=0
    cnt2=0
    for i in range(Ltemp):
        if temp[i]==")":
            cnt1+=1
        else:
            cnt2+=1
        add1="("*cnt1
        add2=")"*cnt2
    ans=add1+S+add2


print(ans)

Submission status: Accepted

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

T = S.copy()

flag = False

#print(S)


for i in range(N):
    flag = False
    i = 0
    while True:
        if i > len(S) - 1:
            break
        if S[i] == '(':
            tmp = i
            flag = True
        if flag and S[i] == ')':
            S.pop(i)
            S.pop(tmp)
            flag = False
        i += 1

#print(S)
#print(T)

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

ans = '('*b + ''.join(T) + ')'*a
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import copy
N = int(input())
S = input()
SS = list(copy.deepcopy(S))
cnt = 0
for i in range(N):
  if S[i] == "(":
    cnt += 1
  else:
    cnt -= 1
  if cnt < 0:
    SS.insert(0,"(")
    cnt = 0
if cnt > 0:
  for j in range(cnt):
    SS.append(")")
print(*SS,sep="")

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = s.count("(")
r = s.count(")")
lmax = 0
if n == 1:
    print("()")
elif l == 0:
    print("("* r + s)
elif r == 0:
    print(s + ")"*l)
else:
    l = 0
    r = 0
    for c in s:
        if c == "(":
            l += 1
        else:
            r += 1
        lmax = max(r-l, lmax,0)
    
    res = "(" * lmax + s 

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

    if l > r:
        res = res + ")" * (l-r)

    elif r > l:
        res = "(" * (r-l) + res

    print(res)

Submission status: Accepted

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

l, r = [], []

for i in range(n):
    if s[i] == '(':
        l.append(i)
    else: r.append(i)

for rv in r[:]:
    if not l: break
    if rv > l[0]:
        r.remove(rv)
        del l[0]

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

Submission status: Accepted

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

while "()" in tmp:
    tmp = tmp.replace("()", "")

left = tmp.count(")")
right = tmp.count("(")
ans = "(" * left + s + ")" * right
print(ans)

Submission status: Accepted

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

c = N
SS = S
while (c > 0):
  SS = SS.replace('()','')
  c = SS.count('()')
print('(' * SS.count(')') + S + ')' * SS.count('('))

Submission status: Accepted

Solution code:

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

rnum = 0
lnum = 0

for i in S:
  if i == ")":
    if lnum > 0:
      lnum -= 1
    else:
      rnum += 1
  
  else:
    lnum += 1
    
ans = ""

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

for i in range(lnum):
  ans += ")"
  
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



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

Submission status: Accepted

Solution code:
n = int(input())
s = input().rstrip()
remaining_l = 0
remaining_r = 0
index = 0
while index < n:
    left = right = 0
    while index < n and s[index] == '(':
        left += 1
        index += 1
    while index < n and s[index] == ')':
        right += 1
        index += 1
    if left > right:
        remaining_r += left - right
    elif left < right:
        k = right - left
        if remaining_r <= k:
            remaining_l += k - remaining_r
            remaining_r = 0
        else:
            remaining_r -= k
print('(' * remaining_l + s + ')' * remaining_r)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = 0
ans = ""
for e in s:
  if e==')':
    if l<=0:
      ans += '('
    else:
      l -= 1
  else:
    l += 1
print(ans + s + ')'*l)

Submission status: Accepted

Solution code:
# 2019/09/20
from collections import deque

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

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

cnt=0
cntL=0

def solve(w,r,s):
    cnt=0
    res=0
    for i in range(n):
        if s[i]==w:
            if cnt:
                cnt-=1
            else:res+=1
        else:
            cnt+=1    
    return list(r*res)




pre=solve(')','(',s)
suf=solve('(',')',s[::-1])
ans=pre+s+suf
print(''.join(ans))