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

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

l = []
r = []
for i in q:
    if i == ")":
        l.append("(")
    else:
        break

for i in q:
    if i == "(":
        r.append(")")

ans = l + list(S) + r
print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


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


def ceil(a, b):
    return (a + b - 1) // b


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

    que = deque()
    for s in S:
        if len(que) == 0:
            que.append(s)
        elif que[-1] == "(" and s == ")":
            que.pop()
        else:
            que.append(s)

    d = defaultdict(int)
    while len(que):
        d[que[-1]] += 1
        que.pop()

    print("(" * d[")"] + S + ")" * d["("])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = input()
b = a

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

left = b.count(")")
right = b.count("(")
l = []
r = []

for i in range(left):
    l.append("(")

for j in range(right):
    r.append(")")

ans = ["".join(l), a, "".join(r)]
print("".join(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = input()
s = input()
num = 0
l = 0
for c in s:
    if c=="(":
        num += 1
    else:
        if num>0:
            num -= 1
        else:
            l += 1
r = num

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

Submission status: Accepted

Solution code:
#グラフを書いて前から順番に埋めていけば良さげ
N = int( input())
S = list( input())
X = [0]
now = S[0]
cnt = 0
for k in S:
    if k != now:
        X.append(cnt)
        now = k
    if k == '(':
        cnt += 1
    else:
        cnt -= 1
else:
    if X[-1] != cnt:
        X.append(cnt)
m = min(X)

if m < 0:
    X = list(map( lambda x: x-m, X))

if X[0] != 0:
    if X[0] <= X[1]:
        X[0] = 0
    else:
        X.insert(0,0)
if X[-1] != 0:
    if X[-2] <= X[-1]:
        X.append(0)
    else:
        X[-1] = 0
L = len(X)
up = 'up'
down = 'down'
updown = up

ans = ''
L = len(X)
for i in range(1,L):
    if updown == up:
        ans += '('*(X[i] - X[i-1])
        updown = down
    else:
        ans += ')'*(X[i-1] - X[i])
        updown = up
print(ans)

Submission status: Accepted

Solution code:
input()
s = input()
kakko =""
num =0
for c in s:
    if c=="(":
        num += 1
    elif num == 0:
        kakko += "("
    else:
        num -=1
print(kakko+s+(")"*num))

Submission status: Accepted

Solution code:
_ = int(input())
s = input()
a = lambda q: q.count('(')-q.count(')')

while True:
    flag = True
    for i in range(len(s)):
        if a(s[:i])<0:
            flag = False
            s = '(' + s
        elif a(s[:i])+a(s[i:])!=0:
            flag = False
            if a(s[:i]) > -a(s[i:]):
                s = s + ')'
            else:
                s = '(' + s
            break
    if flag:
        print(s)
        break

Submission status: Accepted

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

l = 0
r = 0

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

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

Submission status: Accepted

Solution code:
input()

t = ''
c = 0
stock = 0
for s in input():
    if s == ')':
        if c == 0:
            stock += 1
        else:
            t += ')'
            c -= 1
    else:
        if stock:
            t = '(' * stock + t + ')' * stock
            stock = 0
        c += 1
        t += '('
t = '(' * stock + t + ')' * stock + ')' * c
print(t)

Submission status: Accepted

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

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

Submission status: Accepted

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

count,left,right = 0, 0, 0
for i in s:
    if i == ")" and count != 0:
        count -= 1
        right -= 1
    elif i == ")" and count == 0:
        left += 1
    elif i == "(":
        count += 1
        right += 1
print("(" * left + s + ")" * right)

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:
from collections import deque

n=int(input())
s=input()
q=deque([])
t=""

for i in s:
  if i=="(":
    q.append(i)
  else:
    if q:
      q.pop()
    else:
      t+="("
u=")"*len(q)
print(t+s+u)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.MOD


# --------------------------------------------

dp = None


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

    open, close = 0, 0

    for i in range(N):
        if S[i] == "(":
            open += 1
        else:
            if open == 0:
                close += 1
            else:
                open -= 1

    print("(" * close + S + ")" * open)


main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
try:
  migi = s.count("(")
except:
  migi = 0
try:
  hidari = s.count(")")
except:
  hidari = 0
kasa = 0
ans = 0
for i in range(n):
  if s[i] == "(":
    kasa += 1
  else:
    if kasa >= 1:
      ans += 1
      kasa -= 1
migi -= ans
hidari -= ans
print("(" * hidari + s + ")"* migi)

Submission status: Accepted

Solution code:

n = int(input())

s = list(raw_input())
stk = []

i = 0
while i<len(s):
	if s[i] == ')' and not stk:
		s.insert(0,"(")
		i += 1

	if s[i] == ')' and  stk:
		stk.pop()

	if s[i] == '(':
		stk.append('(')
	i += 1

for i in range(len(stk)):
	stk[i] = ')'

print ''.join(s) + ''.join(stk)

Submission status: Accepted

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

cnt = 0
ans = ''
for ch in S:
    if ch == '(':
        cnt = cnt + 1
    if ch == ')':
        cnt = cnt - 1
        
    if cnt == -1:
        cnt = 0
        ans = '(' + ans

    ans = ans + ch


while cnt:
    cnt = cnt - 1
    ans = ans + ')'

print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
S = input()
tmp = 0
MIN = 0
for s in S:
	if s == '(':
		tmp += 1
	else:
		tmp -= 1
	MIN = min(tmp,MIN)

ans1 = ''
if MIN < 0:
	for i in range(-MIN):
		ans1 = ans1 + '('

ans2 = ''
tmp -= MIN
if tmp > 0:
	for i in range(tmp):
	 	ans2 = ans2 + ')'

print(ans1+S+ans2)

Submission status: Accepted

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

level=[0]
for c in S:
	if c=='(':
		level.append(level[-1] + 1)
	else:
		level.append(level[-1] - 1)
numL = min(level)*(-1)
numR = numL + level[-1]
S    = "(" * numL + S + ")" * numR

#print(level)
#print(numL)
#print(numR)
print(S)

Submission status: Accepted

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

ans = s
n_left, n_right = 0, 0
for ss in s:
    if ss == '(':
        n_left += 1
    else:
        if n_left > 0:
            n_left -= 1
        else:
            ans = '('+ans
if n_left > 0:
    for _ in range(n_left): ans += ')'

print(ans)

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(S):
    S = [c for c in S]
    l = []
    r = []
    la = []
    for c in S:
        if c == ')':
            if l:
                l.pop()
            else:
                la.append('(')
        else:
            l.append('(')
    S = la + S + [')' for _ in range(len(l))]
    return ''.join(S)


def main():
    N = read_int()
    S = read_str().strip()

    print(slv(S))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sm = 0
L = 0
s_list = list(S)

for s in s_list:
    if s == "(":
        sm += 1
    else:
        sm -= 1
        if sm < 0:
            L += 1
            sm = 0
            
S = L*"(" + S

r_num = S.count(")")
l_num = S.count("(")

L = max(0, r_num-l_num)
R = max(0, l_num-r_num)


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

Submission status: Accepted

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

    cnt, f = 0, 0
    for i in range(n):
        if s[i] == "(":
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                f += 1
                cnt = 0

    ans = f * "(" + s + cnt * ")"
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def check(s):
    x = 0
    for i in range(len(s)):
        if s[i] == "(":
            x += 1
        else:
            x -= 1

        if x < 0:
            return False

    if x == 0:
        return True
    else:
        return False


def main():
    n, s = int(input()), input()

    ss, q = "", deque()
    for i in range(len(s)):
        if s[i] == "(":
            ss += "("
        else:
            if len(ss) != 0:
                ss += ")"
                if check(ss):
                    q.append(ss)
                    ss = ""
            else:
                ss = "("
                while len(q) != 0:
                    ss += q.popleft()
                ss += ")"
                q.append(ss)
                ss = ""

    if len(ss) != 0:
        c = 0
        for i in range(len(ss)):
            if ss[i] == "(":
                c += 1
            else:
                c -= 1
        ss += ")" * c

    s = ""
    while len(q) != 0:
        s += q.popleft()

    print(s+ss)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x=int(input())
y=input()
A=[]
for i in range(0,x):
  if y[i]=='(':
    A.append(1)
  elif y[i]==")":
    A.append(-1)

st=0

s=0
for i in A:
  if s==0 and i==-1:
    st+=1
  else:
    s+=i

out=''
for i in range(0,st):
  out+='('
for j in A:
  if j==1:
    out+='('
  elif j==-1:
    out+=')'
for i in range(0,s):
  out+=')'
print(out)

Submission status: Accepted

Solution code:
n=int(input())
code=input()
fump=[code[i:i+1] for i in range(0,len(code))]
jump=[]
k=0
l=0
for i in range(n):
    if fump[i]=='(':
        jump.append('(')
        k+=1
    elif k>l:
        jump.append(')')
        l+=1
    else:
        jump.append(')')
        jump.insert(0,'(')
        k+=1
        l+=1
while k>l:
    jump.append(')')
    l+=1
for z in range(len(jump)):
    print(jump[z],end='')

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ss=s
x=0
while x<len(ss)-1:
    if ss[x]=='(' and ss[x+1]==')':
        ss=ss[:x]+ss[x+2:]
        x=0
    else:
        x+=1
left=0
right=0
for i in ss:
    if i=='(':
        right+=1
    elif i==')':
        left+=1
q='('*left
w=')'*right
print(q+s+w)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Stack = ""
for s in S:
    Stack += s
    while len(Stack) >= 2:
        if Stack[-2:] == "()":
            Stack = Stack[:-2]
        else:
            break
c = Stack.count(")")
print("(" * c + S + ")" * (len(Stack) - c))

Submission status: Accepted

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

S_ans = S
count = 0
for i in range(N):
    if S[i]=="(": # > p
        if i>=1 and S[i-1]==")": #m > p
            if count<0:
                S_ans = ("("*abs(count))+S_ans
                count = 0
        count += 1
    else: # > m
        count -= 1
    #print(S[i],count)
        
if count > 0:
    S_ans = S_ans+(")"*abs(count))
else:
    S_ans = ("("*abs(count))+S_ans
    
print(S_ans)

Submission status: Accepted

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

op = 0
add_op = 0
for c in S:
    if c == '(': op += 1
    else: op -= 1
    if op < 0:
        add_op += 1
        op += 1
S = '('*add_op + S

cl = 0
add_cl = 0
for c in S[::-1]:
    if c == ')': cl += 1
    else: cl -= 1
    if cl < 0:
        add_cl += 1
        cl += 1
S += ')'*add_cl

print(S)

Submission status: Accepted

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

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

ans = ("("*left) + S + ")"*cnt
print(ans)

Submission status: Accepted

Solution code:
a=input()
s=input()
s2=0
while s2!=s:
    count=0
    s2=s
    for i in s:
        if i=='(': count+=1
        elif i==')': count-=1
        if count<0: 
            s='('+s
            break
    count=0
    for i in s[::-1]:
        if i==')': count+=1
        elif i=='(': count-=1
        if count<0: 
            s=s+')'
            break
print(s)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
hist = [(0, 0)]
max_dist = 0
for v in s:
    x, y = hist[-1]
    if v == "(": x += 1
    elif v == ")": y += 1
    hist.append((x,y))
    max_dist = max(y - x, max_dist)
lastx , lasty = hist[-1]
print ("(" * max_dist + s + ")" *(lastx - lasty + max_dist))

Submission status: Accepted

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


ev=[0]
for c in s:
    if c=='(':
        ev.append(ev[-1]+1)
    else:
        ev.append(ev[-1]-1)
lowest = -min(ev)


numL = lowest + s.count('(')
numR = s.count(')')

Left = lowest
Right = numL-numR

for i in range(Left):
    print('(',end="")
print(s,end="")
for i in range(Right):
    print(')',end="")
print()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = ""
cur = 0
for i in s:
  if i == "(":
    cur += 1
    ans += i
  else:
    if cur:
      ans += i
      cur -= 1
    else:
      ans = "(" + ans + i
ans += ")" * cur
print(ans)

Submission status: Accepted

Solution code:
def m():
    n = int(input())
    s = str(input())
    exleft = 0
    exright = 0
    for c in s:
        if c == "(":
            exleft +=1

        elif c == ")":
            if exleft <= 0:
                exright +=1
            else:
                exleft -=1
    return "(" * exright + s + ")" * exleft

print(m())

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a, b = 0, 0
for c in s:
    if(c == ')'):
        if(a):
            a -= 1
        else:
            b += 1
    else:
        a += 1
print(b*'('+s+a*')')

Submission status: Accepted

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

mae = S.count("(")
ushiro = N - mae

p_sum = [0] * N

if S[0] == "(":
	p_sum[0] = 1
else:
	p_sum[0] = -1

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

def Good(x):
	if min(x) >= 0 and mae == ushiro:
		return True
	else:
		return False

if not Good(p_sum):
	S = ["("] * (- min(0, min(p_sum))) + S + [")"] * (mae - ushiro - min(0, min(p_sum)))

print("".join(S))

Submission status: Accepted

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

T = 0
ans = []

for s in S:
    if s == "(":
        T += 1
        ans.append("(")
    else:
        T -= 1
        ans.append(")")
        if T < 0:
            ans.insert(0, "(")
            T = 0

for i in range(T):
    ans.append(")")
print("".join(ans))

Submission status: Accepted

Solution code:
n=int(input())
a=input().strip()
x=0
b=[]
for ai in [i for i in list(a)]:
  if ai=='(':
    x+=1
  else:
    x-=1
  b.append(x)
l=b[len(b)-1]	
if min(b)< 0:
  a = '(' * abs(min(b)) + a
  l+=abs(min(b))
a=a+')'*l
    
print(a)

Submission status: Accepted

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

for si in list_s:
    if si == ')':
        if cnt <= 0:
            s = '(' + s
        else :
            cnt -= 1
    
    if si == '(':
        cnt += 1
    
for _ in range(cnt):
    s += ')'

print(s)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
cnt=0
ansP=0
ansA=0
for i in range(N):
  if cnt==0 and S[i]==')':
    ansP+=1
  elif cnt>0 and S[i]==')':
    cnt-=1
  else:
    cnt+=1

cnt=0
Sans=S[::-1]
for i in range(N):
  if cnt==0 and Sans[i]=='(':
    ansA+=1
  elif cnt>0 and Sans[i]=='(':
    cnt-=1
  else:
    cnt+=1

print("("*ansP+S+")"*ansA)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
mi = 0
t = 0
for i in s:
    if i == '(':
        t+=1;
    else:
        t-=1;
        mi = min(mi,t)
if mi<0:
    print('('*-mi,end='')
    print(s+')'*(t-mi))
else:
    print(s+')'*t)

Submission status: Accepted

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

count_end = 0
count = 0
for s in S:
    if s == ')':
        if count > 0:
            count -= 1
        else:
            count_end += 1
    else:
        count += 1

count_begin = 0
count = 0
S.reverse()
for s in S:
    if s == '(':
        if count > 0:
            count -= 1
        else:
            count_begin += 1
    else:
        count += 1
S.reverse()
print (("("*count_end) + "".join(S) +  (")"*count_begin))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a,b,c,d,x = 0,0,0,0,s
for i in s:
	if i=="(": a+=1
	else: b+=1
	if a<b:
		x = "("+x
		a+=1
x = x[::-1]
answer = x
for i in x:
	if i==")": c+=1
	else: d+=1
	if c<d:
		answer = ")"+answer
		c+=1
answer = answer[::-1]
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = list(input())
A = deque()
B = []

left_cnt = 0
right_cnt = 0
for s in S:
    if s == "(":
        left_cnt += 1
        A.append("(")
    else:
        A.append(")")
        if right_cnt + 1 > left_cnt:
            B.append("(")
        else:
            right_cnt += 1

C = [")"] * (left_cnt - right_cnt)
B.extend(A)
B.extend(C)
print("".join(B))

Submission status: Accepted

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

print('(' * add[1] + s + ')'*(cnt[1] -cnt[0]))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
T=S
M=len(T)
while(True):
    T=T.replace("()","")
    if len(T)==M:
        break
    else:
        M=len(T)
k=0
for j in T:
    if j==")":
        k+=1
    else:
        break
print("("*k+S+")"*(M-k))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
now = 0
unclosen = 0
opened = 0
for i in s:
    if i == ")":
        now -= 1
        if opened:
            opened -= 1
        else:
            unclosen += 1
    else:
        now += 1
        opened += 1
print("(" * unclosen + "".join(s) + ")" * opened)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
s = list(input())
j = []
now = 0
unclosen = 0
opened = 0
for i in s:
    if i == ")":
        now -= 1
        if opened:
            opened -= 1
        else:
            unclosen += 1
    else:
        now += 1
        opened += 1
j = np.array(j)
print("(" * unclosen + "".join(s) + ")" * opened)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
S_2 = S[:]
prev = 0
cnt = 0
new_str = []
for i in range(len(S)):
	if S[i] == '(':
		cnt += 1
	else:
		cnt -= 1

	if cnt < 0:
		S_2.insert(0,'(')
		cnt += 1


if cnt > 0:
	for i in range(cnt):
		S_2.append(')')

print(''.join(S_2))

Submission status: Accepted

Solution code:
def d_Insertion(N, S):
    # 解説通り
    d = 0
    x = 0
    for c in S:
        if c == '(':
            d += 1
        else:
            d -= 1
        x = min(x, d)
    ans = '(' * (-x) + S + ')' * (d - x)
    return ans

N = int(input())
S = input().strip()
print(d_Insertion(N, S))

Submission status: Accepted

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


def walk(s):
    """
        Assume that
            up ... '('
            down ... ')'
            start with height 0
            record lowest, endsup.
    """
    height = 0
    lowest = 0
    for x in s:
        if x == '(':
            height += 1
        elif x == ')':
            height -= 1
            lowest = min(height, lowest)
        else:
            pass
    return height, lowest

def inserter(s, height, lowest):
    return '(' * abs(lowest) + s + ')' * (height- lowest)

h, low = walk(s)
print(inserter(s, h, low))

Submission status: Accepted

Solution code:
N = int(input())
s = input()
p = 0
ans = ''
for c in s:
    if c == '(':
        p += 1
    elif c == ')':
        p -= 1
    if p == -1:
        p = 0
        ans = '(' + ans + c
    else:
        ans = ans + c

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

Submission status: Accepted

Solution code:
def wrong(s):
    c = 0

    for x in s:
        if(x == '('):
            c += 1
        elif(x == ')'):
            c -= 1

        if(c < 0):
            return c

    return c

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

w = wrong(s)

while(w):
    if(w > 0):
        s = s + ')'
    elif(w < 0):
        s = '(' + s

    w = wrong(s)

print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
s = input()
c = Counter(s)
ds = c['('] - c[')']
x = min([Counter(s[:i])['('] - Counter(s[:i])[')'] for i in range(n+1)])
print('(' * (-1*x) + s + ')' * (ds - x))

Submission status: Accepted

Solution code:
def main():
    n = input()
    S = input()
    cnt = 0
    m = 0
    for s in S:
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        
        if cnt < 0:
            m += 1
            cnt += 1
            
    ans = "("*m+S+")"*cnt
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc064.contest.atcoder.jp/tasks/abc064_d

"""
import sys
from sys import stdin
input = stdin.readline


def check_balance(S):
    st = 0
    for pos, c in enumerate(S):
        if c == '(':
            st += 1
        else:                   #  ')'
            st -= 1
            if st < 0:
                break
    return st


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

    result = check_balance(S)
    while result != 0:
        if result < 0:
            S = '(' + S
        elif result > 0:
            S = S + ')'
        result = check_balance(S)

    print(S)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

Sold = S
while True:
    Snew = Sold.replace('()', '')
    if len(Snew) == len(Sold):
        break
    Sold = Snew

num = Snew.count(')')
print('(' * num + S + ')' * (len(Snew) - num))

Submission status: Accepted

Solution code:
n = int(input())
N = input()
L = 0
R = 0
num = 0
for c in N:
    if c == '(':
        num += 1
    else:
        if num:
            num -= 1
        else:
            L += 1
R = num

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

Submission status: Accepted

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

c,L,R = 0,0,0
for i in range(N):
    if S[i] == "(":
        c += 1
    else:
        c -= 1
    if c < 0:
        L += 1
        c = 0

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

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

Submission status: Accepted

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

Submission status: Accepted

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

unpair = 0
left = 0
right = 0
for c in s:
    if(c == "("):
        unpair += 1
    else:
        if(unpair):
            unpair -= 1
        else:
            left += 1
right = unpair

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

Submission status: Accepted

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

a = 0
b = 0

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

Submission status: Accepted

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

def count(s, k):
    c, needs = 0, 0
    for i in s:
        if i != k:
            if c <= 0:
                needs += 1
            else:
                c -= 1
        else:
            c += 1
    return needs

l = count(s, '(')
r = count(s[::-1], ')')
print('('*l + s + ')'*r)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
stack=[]
l=0
r=0
for c in s:
    if len(stack)>0 and stack[-1]=='(' and c==')':
        stack.pop()
    else:
        stack.append(c)
if len(stack)==0:
    print(s)
else:
    for c in stack:
        if c==')':
            l+=1
        else:
            r+=1
    print('('*l+s+')'*r)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    S = input()
    t = S[:]
    while True:
        change = False
        for i in range(1, len(t)):
            if (t[i - 1], t[i]) == ("(", ")"):
                t = t[:i - 1] + t[i + 1:]
                change = True
                break
        if not change:
            break

    a = "(" * t.count(")")
    b = ")" * t.count("(")
    print(a + S + b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
count_1 = 0
count_2 = 0
for kigou in input_line_2:
	if kigou == "(":
		count_2 += 1
	if kigou == ")":
		if count_2 > 0:
			count_2 -= 1
		else:
			count_1 += 1
	#print kigou, count_1, count_2
print count_1 * "(" + input_line_2 + count_2 * ")"

Submission status: Accepted

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

def count_need(string, from_left=True):
    savings = 0
    ng = 0
    
    if from_left == False:
        key = '('
    else :
        key = ')'

    for s in string:
        if (s == key):
            if savings <= 0: 
                ng += 1
            else:
                savings -= 1
        else:
            savings += 1
    return ng

left_num = count_need(S, from_left=True)
right_num = count_need(S[::-1], from_left=False)

print("("*left_num + S + ")"*right_num)