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 math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

N = i_inpl()
S = input()

r, l = 0, 0

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

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

Submission status: Accepted

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

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
print("("*b+s+")"*a)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
l = []
count1 = 0
count2 = 0
for i in range(n):
    if s[i] == ")":
        if count2 == 0:
            l.append("(")
        else:
            count2 = count2 - 1
    else:
        count2 = count2 + 1
if count2 > 0:
    l2 = [")"]*count2
    ans = l + s + l2
    for i in ans:
        print(i, end = "")
else:
    ans = l + s
    for i in ans:
        print(i, end = "")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
n = int(input())
s = input()
ans = copy.deepcopy(s) 
flag = True
while flag:
    flag = False
    for i in range(len(s)-1):
        if s[i] == '(' and s[i+1] == ')':
            s = s[:i] + s[i+2:]
            flag = True
            break


for i in range(len(s)):
    if s[i] == "(":
        ans += ")"
    elif s[i] == ")":
        ans = "(" + ans


print(ans)

Submission status: Accepted

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

a = []
for i in s:
    if a and a[-1] == "(" and i == ")":
        a.pop()
    else:
        a.append(i)

c = a.count("(")
d = a.count(")")


print("("*d+s+")"*c)

Submission status: Accepted

Solution code:
import numpy as np
import copy


def dfs(adj_list, cur_node, visited_nodes):
    visited_nodes.append(cur_node)

    # next_nodes = np.argwhere(adj_mat[cur_node] != 0).flatten()
    next_nodes = adj_list[cur_node]

    if len(next_nodes) == 0:
        # N
        visited_nodes.remove(cur_node)
        return 0

    for tup in next_nodes:
        if tup[0] in visited_nodes:
            visited_nodes.remove(cur_node)
            return np.inf

    # score_max = max([dfs(adj_list, b, visited_nodes) + c
    #                  for b, c in next_nodes])
    scores = []
    for b, c in next_nodes:
        score = dfs(adj_list, b, visited_nodes) + c
        if np.isinf(score):
            visited_nodes.remove(cur_node)
            return np.inf
        scores.append(score)

    score_max = max(scores)

    visited_nodes.remove(cur_node)
    return score_max


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

    y_max = 0
    y = 0
    for c in S:
        if c == '(':
            y -= 1
        else:
            y += 1

        if y > y_max:
            y_max = y

    S_ans = ''
    if y_max > 0:
        S_ans += '(' * y_max
        y -= y_max

    S_ans += S

    if y < 0:
        S_ans += ')' * (-y)

    # if __debug__:
    #     y_max = 0
    #     y = 0
    #     for c in S_ans:
    #         if c == '(':
    #             y -= 1
    #         else:
    #             y += 1

    #         if y > y_max:
    #             y_max = y

    #         assert y <= 0

    #     assert y_max == 0

    print(S_ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    _ = int(input())
    S = input()
    a = 0
    b = 0
    for s in S:
        if s == '(':
            b += 1
            continue
        if s == ')' and b == 0:
            a += 1
            continue
        b -= 1
    print('(' * a + S + ')' * b)


main()

Submission status: Accepted

Solution code:
_=input()
S=input()
cnt,ladd,radd=0,0,0
for c in S:
    if c=="(":
        cnt+=1
    elif c==")":
        if cnt==0:
            ladd+=1
        else:
            cnt-=1
radd=cnt
print("("*ladd + S + ")"*radd)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
p = ["(", ")"]
l = 0
n = 0
for i in range(N - 1, -1, -1):
  if S[i] == p[1]:
    l += 1
  else:
    if l > 0:
      n += 2
      l -= 1

r = N - n - l
print(p[0] * l + S + p[1] * r)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
S = input()
m = Counter(S)
cnt_set = 0
cur = 0
for x in S:
    if x == '(':
        cur += 1
    else:
        if cur > 0:
            cnt_set += 1
            cur -= 1
ans = '('*(m[')']-cnt_set) + S + ')'*(m['(']-cnt_set)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = input()
d = deque()
cnt = 0
for x in S:
    if x == '(':
        d.append(1)
    elif x == ')' and d:
        d.pop()
    else:
        cnt += 1
print('(' * cnt + S + ')' * len(d))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
_S = S
while '()' in S:
    for i in range(len(S)-1):
        if S[i] =='(' and S[i+1] == ')':
            S = S[:i] + S[i+2:]
            break
c1 = S.count(')')
c2 = S.count('(')
print('(' * c1 + _S + ')' * c2)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = input()
q = deque()
r = ""
l = ""
for i in s:
    if i == ")":
        if not q:
            r+="("
        else:
            q.pop()
    else:
        q.append("(")
while q:
    q.pop()
    l+=")"
print(r+s+l)

Submission status: Accepted

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

back = 0
front = 0
for k in s:
    if k == '(':
        back += 1
    else:
        back -= 1
        while back < 0:
            front += 1
            back += 1
f = ""
for i in range(front):
    f = f + '('
b = ""
for i in range(back):
    b = b + ")"
s = f + s + b
#print(len(s))
print(s)

Submission status: Accepted

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

cnt_l = 0
min_h = 0

for ch in S:
    if ch == '(':
        cnt_l += 1
    else:
        cnt_l -= 1
    min_h = min(min_h, cnt_l)
    
print('('*(-min_h) + S + ')'*(cnt_l-min_h))

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n = II()
s = IS()
cnt = 0
ans = s
for c in s:
    if c == '(':
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:
            ans = '(' + ans
cnt = 0
for c in s[::-1]:
    if c == ')':
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:
            ans = ans + ')'
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
LIST=[]

i=0
while i<N:
    if i<=N-1 and len(LIST)>=1 and LIST[-1]=="(" and S[i]==")":
        i+=1
        LIST.pop()
    else:
        LIST.append(S[i])
        i+=1

print("("*LIST.count(")")+S+")"*LIST.count("("))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
now = [0]
newS = ""
for s in S:
    if s == "(":
        now.append(now[-1] + 1)
    else:
        now.append(now[-1] - 1)
        
if min(now) < 0:
    newS += "(" * abs(min(now))
newS += S
if now[-1]+abs(min(now)) > 0:
    newS += ")" * (now[-1]+abs(min(now)))
print(newS)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
mae=0
ushi=0
ans0=0
ans1=0
ans01=[]
flag=False
for i in range(n):
    ans01.append(s[i])
    if s[i]=='(':
        mae+=1
        flag=True
        ans1+=1
    else:
        ushi+=1
        if flag:
            ans1-=1
            if ans1<=0:
                flag=False
    ans0=max(ushi-mae,ans0)
ans00=[]
ans11=[]
for i in range(ans0):
    ans00.append('(')
for i in range(ans1):
    ans11.append(')')

print(''.join(ans00+ans01+ans11))

Submission status: Accepted

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

cnt = 0
for i,s in enumerate(S):
    if cnt < 0:
        ans = ['('] + ans
        cnt = 0
    if s == '(':
        cnt += 1
    else:
        cnt -= 1
if cnt> 0:
    ans = ans + [')'] * cnt
elif cnt < 0:
    ans = ['('] * (-cnt) + ans
print(''.join(ans))

Submission status: Accepted

Solution code:

def main():
    num = int(input())
    data = list(input())

    left, righ = 0, 0
    for i in range(num):
        ele = data[i]
        if ele == '(':
            righ += 1
        else:
            if righ > 0:
                righ -= 1
            else:
                left += 1

    ans = ['(' for i in range(left)] + data + [')' for i in range(righ)]
    print(''.join(ans))






if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n = int(input())
    s = input()
    count = 0
    new_left = 0
    new_right = 0

    # See:
    # https://www.youtube.com/watch?v=5FOTOiV5p0U
    for si in s:
        if si == '(':
            count += 1
        else:
            count -= 1

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

    new_right = count

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = S

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

print("(" * t.count(")") + S + ")" * t.count("("))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, S: str):
    pre = 0
    op = 0
    for c in S:
        if c == '(':
            op += 1
        elif c == ')':
            if op > 0:
                op -= 1
            else:
                pre += 1
    ret = (''.join(['(' for _ in range(pre)]) + S + 
           ''.join([')' for _ in range(op)]))
    print(ret)
    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:
from copy import deepcopy

N = int(input())
S = list(input())
newS = deepcopy(S)

i = 0
while 1:
    if i >= len(S):
        break
    if S[i] == "(":
        j = i
        while 1:
            if j >= len(S):
                break
            if S[j] == ")":
                S.pop(j)
                S.pop(i)
                i = -1
                break
            j += 1
    i += 1

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

print("(" * x + "".join(newS) + ")" * y)

Submission status: Accepted

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

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

if maxcount > 0:
    S = "(" * maxcount + S

count = 0
maxcount = 0

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

if count > 0:
    S += ")" * count

print(S)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  s=S()

  c=0
  f=''
  e=''
  
  for x in s:
    if x=='(':
      c+=1
    else:
      c-=1

    if c<0:
      f+='('*abs(c)
      c=0

  if c<0:
    f+='('*abs(c)
  else:
    e+=')'*c

  return f+s+e

print(main())

Submission status: Accepted

Solution code:
n=int(input())
s=input()
s2=''
flag=0
cnt=0
for i in range(n):
  if flag==0:
    if s[i]=='(':
      flag=1
      cnt+=1
    elif s[i]==')':
      s2+=')'
  elif flag==1:
    if s[i]=='(':
      cnt+=1
    elif s[i]==')':
      cnt-=1
    if cnt==0:
      flag=0
if flag==1:
  s2+='('*cnt
cntl=0
cntr=0
for i in range(len(s2)):
  if s2[i]=='(':
    cntr+=1
  elif s2[i]==')':
    cntl+=1
ans='('*cntl+s+')'*cntr
print(ans)

Submission status: Accepted

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

leftStack = []
for i in range(len(S)):
    s = S[i]
    if s == "(":
        leftStack.append(s)
    elif s == ")":
        if len(leftStack) > 0:
            leftStack.pop()
        else:
            ans = "(" + ans

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

Submission status: Accepted

Solution code:
from functools import reduce

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

# 閉じられていない '(' の個数だけ S の末尾に ')' を、
# 閉じられていない ')' の個数だけ S の先頭に '(' を付与した文字列が解である
a, b = reduce(
    lambda acc, s:
        (
            (
                acc[0] + 1 if s == '(' else
                max(0, acc[0] - 1)
            ),
            (
                acc[1] + 1 if s == ')' and acc[0] == 0 else
                acc[1]
            )
        ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'

# 出力
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

# 閉じられていない '(' の個数だけ S の末尾に ')' を、
# 閉じられていない ')' の個数だけ S の先頭に '(' を付与した文字列が解である
a, b = reduce(
    lambda acc, s: (
        (
            acc[0] + 1 if s == '(' else
            max(0, acc[0] - 1)
        ),
        (
            acc[1] + 1 if s == ')' and acc[0] == 0
            else acc[1]
        )
    ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'

# 出力
print(ans)

Submission status: Accepted

Solution code:
N = input()

cnt = 0
s = ""
for x in input():
  if x == "(":
    cnt += 1
  else:
    cnt -= 1
    if cnt < 0:
      cnt += 1
      s = "(" + s
  s += x
for _ in range(cnt):
  s += ")"
print(s)

Submission status: Accepted

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

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

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

for _ in range(l):
  s = s+")"
  
for _ in range(r):
  s = "(" + s
  
  
print(s)

Submission status: Accepted

Solution code:
kakko=[0]*(int(input())+1)
S=input()
kakkoSum=0
for n,s in enumerate(S):
    if s=="(":
        kakkoSum +=1
    else:
        kakkoSum -=1
    kakko[n+1] = kakkoSum
D=min(kakko)
if D<0:
    d=kakko[-1]
    kakkoleft=-D
    kakkoright=-D+d
    print("(" * kakkoleft + S + ")" * kakkoright)
elif kakko[-1] ==0:print(S)
else:
    d=kakko[-1]
    print(S + ")"* d)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
open_ = 0
close_ = 0
for char in s:
    if char == "(":
        open_ += 1
    else:
        if open_ > 0:
            open_ -= 1
        else:
            close_ += 1
for i in range(open_):
    s += ")"
for i in range(close_):
    s = "(" + s
print(s)

Submission status: Accepted

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

cnt = 0
ans = ''
for c in S:
    if c == '(':
        cnt += 1
    if c == ')':
        cnt -= 1
    if cnt < 0:
        cnt += 1
        ans += '('
ans += S + ')' * cnt
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

left = 0
max_left = 0

for i in S:
    if i == ')':
        left += 1
        max_left = max(max_left, left)
    else:
        left -= 1

right = 0
max_right = 0

for i in S[::-1]:
    if i == '(':
        right += 1
        max_right = max(max_right, right)
    else:
        right -= 1

ans = '(' * max_left  + S +  ')' * max_right

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
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 [input() 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()
    imos = []
    for s in S:
        if s == "(":
            imos.append(1)
        else:
            imos.append(-1)
    status = [0]
    head = ""
    tail = ""
    for imo in imos:
        appp = status[-1] + imo
        if appp < 0:
            head += "("
            appp = 0
        status.append(appp)
    if status[-1] > 0:
        tail = ")" * status[-1]
    print(head+S+tail)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)

def main():
    input()
    s=input()
    t=s
    while "()"in s:
        s=s.replace("()","")
    n,m=s.count(")"),s.count("(")
    s=n*"("+t+m*")"
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

li_start = []
li_end = []
for ind,i in enumerate(S):
    if(i=='('):
        li_start.append(ind)
    else:
        if(len(li_start)>0):
            li_start.pop(-1)
        else:
            li_end.append(ind)
print('('*len(li_end)+S+')'*len(li_start))

Submission status: Accepted

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

num = 0
lmax = 0
rmax = 0
for i in range(n):
    if s[i] == ")":
        num += 1
    else:
        num -= 1
    lmax = max(lmax, num)

num = 0
for i in range(n-1, -1, -1):
    if s[i] == "(":
        num += 1
    else:
        num -= 1
    rmax = max(rmax, num)

print("("*lmax + s + ")"*rmax)

Submission status: Accepted

Solution code:
import collections

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

num_open = 0
num_close = 0

q = collections.deque([])

for i in range(N):
  if S[i] == "(":
    q.append("(")
  if S[i] == ")":
    if len(q) == 0:
      num_close += 1
    else:
      q.pop()

num_open = len(q)
str_close = "(" * num_close
str_open =  ")" * num_open


ans = str_close + S + str_open

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
num_overopen = 0
num_overclose = 0
import collections
q = collections.deque([])
for i in range(n):
    if s[i] == "(":
        q.append("(")
    if s[i] == ")":
        if len(q) == 0:
            num_overclose += 1
        else:
            q.pop()
print( ("(" * num_overclose) + s + (")" * len(q)))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = 0
y = 0
for i in range(n):
    if s[i] == '(':
        x += 1
    elif s[i] == ')':
        x -= 1
    if x < 0:
        y += 1
        x += 1
print('(' * y + s + ')' * x)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
s1 = [1 if si=='(' else -1 for si in s]
cnt1=0#( のカウント
cnt2=0
ans1=0
ans2=0
for i in range(n):
    if s1[i]==1and cnt2>0:
        ans2+=cnt2
        cnt2 = 0
    cnt2+=-s1[i]
if cnt2>0:
    ans2+=cnt2
for i in range(n)[::-1]:
    if s1[i]==-1and cnt1>0:
        ans1+=cnt1
        cnt1 = 0
    cnt1+=s1[i]
if cnt1>0:
    ans1+=cnt1
s=['(']*ans2+s+[')']*ans1
print(''.join(s))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
S = list(input())
ANS = []
a = 0
b = 0
for s in S:
    ANS.append(s)
    if s == '(':
        a += 1
        #print(ANS)
    else:
        b += 1
        if a<b:
            a += 1
            ANS.insert(0,'(')
        #print(ANS)
for i in range(a-b):
    ANS.append(')')
print("".join(ANS))

Submission status: Accepted

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

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

print('('*(-x) + S + ')'*(d-x))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x, y, a = 0, 0, 0

for char in s:
    if char == '(': x += 1
    else: y += 1
    a = min(a, x-y)
    b = x-y

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc064/tasks/abc064_d

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math
import heapq

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

    need_left = 0
    need_right = 0
    for s in S:
        if s == '(':
            need_right += 1
        else:
            if need_right == 0:
                need_left += 1
            else:
                need_right -= 1

    ans = '(' * need_left + S + ')' * need_right
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mi = 0
ma = 0
c = 0
for it in S:
  if it == '(':
    c +=1
  else:
    c -=1
  mi = min(c,mi)
  ma = max(c,ma)

print ( "("*( max(-mi,0) ) + S + ")"*( max(c-mi,0)  ) )

Submission status: Accepted

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

Submission status: Accepted

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

left = 0
stack = []
for i in range(n):
    if s[i] == '(':
        stack.append('(')
    else:
        if len(stack) == 0:
            left += 1
        else:
            stack.pop()
right = len(stack)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

pares = S[:]

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)
        
min_num = min(pares_num)
if min_num < 0:
    pares = '(' * (-1*min_num) + pares
    

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)
#print(pares)
#print(pares_num)

pares += ')' * pares_num[-1]


print(pares)

Submission status: Accepted

Solution code:
from functools import reduce

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

# 閉じられていない '(' の個数だけ S の末尾に ')' を、
# 閉じられていない ')' の個数だけ S の先頭に '(' を付与した文字列が解である
a, b = reduce(
    lambda acc, s: (
        (
            acc[0] + 1 if s == '(' else max(0, acc[0] - 1),
            acc[1] + 1 if s == ')' and acc[0] == 0 else acc[1]
        )
    ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'

# 出力
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
X=[0]
r=0
for i in range(n):
  if s[i]=="(":
    r+=1
  else:
    r-=1
  X.append(r)
left=-min(X)
right=X[-1]+left
print("("*left+s+")"*right)

Submission status: Accepted

Solution code:
input()
S = input()
q = [-1]
for c in S:
    if c == ")" and q[-1] == 0:
        q.pop()
    elif c ==")":
        q.append(1)
    else:
        q.append(0)
print("("*q.count(1)+S+")"*q.count(0))

Submission status: Accepted

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

l = 0
r = 0

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

print('('*l+''.join(S)+')'*i)

Submission status: Accepted

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

T = [+1 if s=='(' else -1 for s in S]

from itertools import accumulate
Tcumsum = list(accumulate(T))

i = max(0, - min(Tcumsum))

print('(' * i + S + ')' * (Tcumsum[-1]+i))