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:
def main():
    n = int(input())
    S = input()
    a, b = 0, 0
    aa = 0
    m = 0
    for s in S:
        if aa > 0 and s == ')':
            m += 1
            aa -= 1
        if s == '(':
            a += 1
            aa += 1
        else:
            b += 1
    print(''.join(['(' * (b - m), S, ')' * (a - m)]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

L, R = 0, 0
cnt = 0
for s in S:
    if s == '(':
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:
            L += 1

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = list(input())
d = deque(s)
l, r = 0, 0
for i in range(n):
    if l == r and s[i] == ")":
        d.appendleft("(")
    elif s[i] == ")":
        r += 1
    else:
        l += 1
s = "".join(list(d))
print(s + ")" * max(0, l - r))

Submission status: Accepted

Solution code:
# は？
# 挿入とか言っときながら両端に加えることしかできなさそう(理屈は不明)
# 479836982452回やってもわからん ほぼ勘とサンプルの試行錯誤でガチャっただけ
n = int(input())
s = list(input())
surplus_left, surplus_right = 0, 0
right_count, left_count = 0, 0
for i in range(n - 1, -1, -1):
    if s[i] == "(":
        if left_count > 0:
            left_count -= 1
        else:
            surplus_left += 1
    else:
        left_count += 1
for i in range(n):
    if s[i] == ")":
        if right_count > 0:
            right_count -= 1
        else:
            surplus_right += 1
    else:
        right_count += 1

print("(" * surplus_right + "".join(s) + ")" * surplus_left)

Submission status: Accepted

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

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

LR[1]=count
for i in range(2):
    for j in range(LR[i]):
        if i==0:
            S.insert(0,"(")
        else:
            S.append(")")

print("".join(S))

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:
      r-=1
    else:
      l+=1
  else:
    r+=1
for _ in range(l):
  print('(', end='')
print(S, end='')
for _ in range(r):
  print(')', end='')

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  S = list(str(input()))
  num_1 = 0
  num_2 = 0
  for i in range(N):
    if S[i] == '(':
      num_1 += 1
    else:
      if num_1 > 0: num_1 -= 1
  for i in range(N-1, -1, -1):
    if S[i] == ')':
      num_2 += 1
    else:
      if num_2 > 0: num_2-=1
  for i in range(num_1):
    S.append(')')
  for i in range(num_2):
    S.insert(0, '(')
  print(''.join(S))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n = int(input())
S = input()
"""
)))((()())
-3  -1  
左に何個、右に何個
"""
l = 0
r = 0
prev = ")"

for s in S:
    if prev == ")" and s == ")":
        if r > 0:
            r -= 1
        else:
            l += 1
    elif prev == ")" and s == "(":
        r += 1
    elif prev == "(" and s == ")":
        r -= 1
    elif prev == "(" and s == "(":
        r += 1
    # print(s,l,r)
    prev = s
ans = "("*l + S + ")"*r
# print(l,r)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
ns = s
while '()' in ns:
    ns = ns.replace('()', '')
l = ns.count(')')
r = ns.count('(')
print('(' * l + s + ')' * r)

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    S = input()
    left, right, cnt = 0,0,0

    for s in S:
        if s == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            right += 1
            cnt = 0

    if cnt>0:
        left = cnt

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
now=0
rec=0
for i in s:
    now+=(-1)**(i==")")
    rec=min(now,rec)
f,t="",""
if rec<0:
    f="("*-rec
    now-=rec
if now>0:
    t=")"*now
print(f+s+t)

Submission status: Accepted

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

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

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

ans = "("*left_ans + S + ")"*right_ans
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    S = list(input())
    Stmp = S.copy()
    Stmp = deque(Stmp)
    cnt = 0
    for s in S:
        cnt += (s=='(') - (s==')')
        if cnt < 0:
            Stmp.appendleft('(')
            cnt += 1
    for _ in range(cnt):
        Stmp.append(')')
    print(''.join(Stmp))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    h_left, h_min, h_cur = 0, 0, 0
    for c in S:
        if c == '(':
            h_cur += 1
        else:
            h_cur -= 1
        h_min = min(h_min, h_cur)
    h_right = h_cur
    if h_min < 0:
        h_left -= h_min
        h_right -= h_min
    print('(' * h_left + S + ')' * h_right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
cnt=0
right=0
left=0
for i in range(len(s)):
    if s[i] == '(':
        cnt+=1
    else:
        cnt-=1
    if cnt < 0:
        right+=1
        cnt=0
if cnt>0:
    left=cnt
for i in range(right):
    s.insert(0,'(')
for i in range(left):
    s.append(')')
print(''.join(s))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=0
x=""
y=""
for i in range(n):
    if s[i]=="(":
        a+=1
    else:
        a-=1
if a>0:
    s=s+")"*a
elif a<0:
    s="("*abs(a)+s
#print(s)
t=0

while t==0:
    b=0
    for i in range(len(s)):
        if s[i]=="(":
            b+=1
        else:
            b-=1
        if b<0:
            s="("+s+")"
            #print(s)
            break
    if b==0:
        break
print(s)

Submission status: Accepted

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

l = "("
r = ")"

add_right, add_left = 0, 0

for c in s:
    if c == l:
        add_right += 1
    else:
        if add_right:
            add_right -= 1
        else:
            add_left += 1

print(l * add_left + s + r * add_right)

Submission status: Accepted

Solution code:
N=int(input())
n=input()
l=0;r=0
for i in n:
    if i=="(":
        r+=1
    else:
        if r:
            r-=1
        else:
            l+=1
print("("*l+n+")"*r)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    s = input()[:-1].decode()
    c1 = 0
    c2 = 0
    for i in range(n):
        if s[i] == '(':
            c1 += 1
        elif s[i] == ')':
            c1 -= 1
        if c1 < 0:
            c1 = 0
            c2 += 1
    print('(' * c2, s, ')' * c1, sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

left=0
right=0
for s_i in s:
    if s_i=='(':
        right+=1
    elif s_i==')':
        if right>0:
            right-=1
        else:
            left+=1

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

Submission status: Accepted

Solution code:
n = int(input())
string = input()
start_cnt = 0
end_cnt = 0
tmp = 0
for s in string:
    if s == ")":
        if tmp == 0:
            start_cnt += 1
        else:
            tmp -= 1
    else:
        tmp += 1
tmp = 0
for s in string[::-1]:
    if s == "(":
        if tmp == 0:
            end_cnt += 1
        else:
            tmp -= 1
    else:
        tmp += 1
for _ in range(start_cnt):
    print("(", end = "")
    
print(string, end = "")

for _ in range(end_cnt):
    print(")", end = "")
    
print()

Submission status: Accepted

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

ans = ''

lcount = 0
rcount = 0
now = 0
for i in range(N):
  si = S[i]
  if (lcount==0) and (si==')'):
    rcount += 1
    ans = '(' + ans + ')'
  elif si == ')':
    lcount -= 1
    ans = ans + ')'
  
  if (rcount>=1) and (si=='('):
    rcount = 0
    lcount = 1
    ans = ans + '('
  elif si == '(':
    ans = ans + '('
    lcount += 1
    

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
S = S()

MIN = 0
SUM = 0

for s in S:
  if s == "(":
    SUM += 1
  else:
    SUM -= 1
    MIN = min(MIN,SUM)
print("("*abs(MIN)+S+")"*(SUM-MIN))

Submission status: Accepted

Solution code:
input()
s=t=input()
p,q=o="()"
exec('s=s.replace(o,"");'*50)
f=s.count
print(p*f(q)+t+q*f(p))

Submission status: Accepted

Solution code:
input()
t=s=input()
p,q=o="()"
while o in s:s=s.replace(o,"")
f=s.count
print(p*f(q)+t+q*f(p))

Submission status: Accepted

Solution code:
input()
t=s=input()
p,q=o="()"
while o in s:s=s.replace(o,"")
print(p*s.count(q)+t+q*s.count(p))

Submission status: Accepted

Solution code:
input()
t=s=input()
while"()"in s:s=s.replace("()","")
print("("*s.count(")")+t+")"*s.count("("))

Submission status: Accepted

Solution code:
input()
s = input()
L = R = 0
for t in s:
    if t == "(":
        R += 1
    else:
        if R:
            R -= 1
        else:
            L += 1
print("("*L + s + ")"*R)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    s = list(input())

    open_cnt = 0
    close_cnt = 0
    for si in s:
        if si == "(":
            open_cnt += 1
        else:
            if open_cnt == 0:
                close_cnt += 1
            else:
                open_cnt -= 1


    for i in range(close_cnt):
        s.insert(0, "(")

    for i in range(open_cnt):
        s.append(")")

    print(*s, sep="")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 括弧が開いている数を左からカウント
# "("が0の状態で")"が来たらopen状態は変えずにその数をカウント・・・A
# 最終的にかっこが開いている数をカウント・・・B
# Aの数だけ"("を左端に追加
# Bの数だけ")"を右端に追加

import sys
readline = sys.stdin.readline

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

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

    print("("*need_left+s+")"*left_left)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

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

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

    print("("*need_left+s+")"*need_right)

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
s = ns().strip()
h = 0
minh = 0
for c in s:
    if c == "(":
        h += 1
    else:
        h -= 1
    minh = min(minh, h)
print("("*(-minh) + s + ")"*(h-minh))
#括弧列では、任意の接頭辞で、"("の方が多いこと、かつ全体で(と)の数が等しいことが必要なので、そうなる条件を考える。
#一番バランスが悪いところに合わせて(を先頭からならべ、後方に)を並べて整合性を取ればよく、その方法が辞書順最小であることが示される(解説参照)
#括弧列に関してあまり考えずに逆算してしまった。

Submission status: Accepted

Solution code:
n=int(input())
s=input()
stack=0
needleft=0
needright=0
for c in s:
    if c=='(':
        needright+=1
    else:
        if needright>0:
            needright-=1
        else:
            needleft+=1
s='('*needleft+s
s+=')'*needright
print(s)

Submission status: Accepted

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

while True:
    cum=[0]*(len(s)+1)
    for i,c in enumerate(s):
        cum[i+1]=cum[i]-1 if c==')' else cum[i]+1
    min_=min(cum)
    if min_<0:
        s='('*abs(min_)+s
        continue
    r=cum[-1]
    if r>0:
        s=s+')'*r
        continue
    print(s)
    exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    S = input()
    par = [0]
    cc = 0
    for i in S:
        if i == '(': cc += 1
        else: cc -= 1
        par.append(cc)

    mp = min(par)
    output = S
    if mp < 0: output = '(' * abs(mp) + output
    if abs(mp) + cc > 0: output = output + ')' * (abs(mp)+cc)
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

stack = []
for s_i in S:
    if not stack:
        stack.append(s_i)
    elif stack[-1] == "(" and  s_i == ")":
        stack.pop()
    else:
        stack.append(s_i)

# 余っている左、右のカッコの数 
left = 0
right = 0
for s_i in stack:
    if s_i == ")":
        right += 1
    else:
        left += 1

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

Submission status: Accepted

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

data = [0, 0]  # [, ] = num of ( and )
temp = -1
for i in range(n):
    temp += 1
    tar = s[temp]
    if (tar == '('):
        data[0] += 1

    else:
        if (data[0] > data[1]):
            data[0] -= 1
        else:
            s = '(' + s
            temp += 1


add = ')' * data[0]
s = s + add

print(s)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    N=II()
    S=input()
    p = 0
    num_right_p = 0
    ans = ''
    r = 0
    for s in S:
        if s == '(':
            p += 1
        else:
            if p > 0:
                p -= 1
            else:
                r += 1

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

    
main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n = ni()
s = ns()

q = deque()
for i in range(n):
    p = q.pop() if len(q) else '$'
    if not (p == '(' and s[i] == ')'):
        if p != '$':
            q.append(p)
        q.append(s[i])

ans = deque(s)
for c in q:
    if c == ')':
        ans.appendleft('(')
    else:
        ans.append(')')

print(*ans, sep="")

Submission status: Accepted

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

stock = 0
L_cnt = 0
for s in S:
    if s == "(":
        stock += 1
    if s == ")":
        if stock == 0:
            L_cnt += 1
        else:
            stock -= 1

print("(" * L_cnt + S + ")" * stock)

Submission status: Accepted

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

nopen = 0
sl = ''
sr = ''

for c in s:
    if c == '(':
        nopen += 1
    else:
        if nopen == 0:
            sl += '('
        else:
            nopen -= 1

nopen = sum([1 if c == '(' else -1 for c in sl + s])
sr = ')' * nopen


print(sl + s + sr)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def preprocess(seq, n):
        stripped = False
        for i in range(n-1):
            if seq[i] == '(' and seq[i+1] == ')':
                new_seq = seq[:i] + seq[i+2:]
                stripped = True
                break
        if stripped:
            return preprocess(new_seq, n-2)
        else:
            return seq
        

    n = ii()
    initial = input()
    L = list(initial)

    stripped = preprocess(L, n)
    # print(stripped)
    left_p = stripped.count(')')
    right_p = stripped.count('(')

    print('(' * left_p + initial + ')' * right_p)

    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
c = 0
l = []
for i in S:
    if i == "(":
        c += 1
    else:
        c -= 1
    l.append(c)

m = min(l)
if m < 0:
    for i in range(N):
        l[i] += (-m)

    M = l[-1]
    ans = ["("] *(-m) + S + [")"] *M
    
else:
    M = l[-1]
    ans = S + [")"] *M

output = "".join(ans)
print(output)

Submission status: Accepted

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

Submission status: Accepted

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

left = 0
p = 0
for i in range(n):
    if s[i] == '(':
        p += 1
    else:
        if p == 0:
            left += 1
        else:
            p -= 1
right = p

res = ""
for i in range(left):
    res += '('
res += s
for i in range(right):
    res += ')'
print(res)

Submission status: Accepted

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

minv = 0
score = 0
for i in range(n):
    if s[i] == '(':
        score += 1
    else:
        score -= 1
    minv = min(minv, score)

ans = ""
for i in range(0, -minv):
    ans += "("
ans += s
for i in range(0, score-minv):
    ans += ")"
print(ans)

Submission status: Accepted

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

x=0
y=0

for i in S:
    if i=="(":
        x+=1
    else:
        if x<=0:
            y+=1
        else:
            x-=1
print("("*y+S+")"*x)

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:
            b += 1
        else:
            a -= 1

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


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


i=0
c=0
while i<len(s):
    if s[i]=="(" and c<0:
        s="("*(-c)+s
        i-=c
        c=0
    elif s[i]=="(":
        c+=1
        i+=1
    else:
        c-=1
        i+=1

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

Submission status: Accepted

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

for i in range(1+n//2):
    ss = ss.replace("()","")

sta = ss.count("(")
end = ss.count(")")

print("("*end + s + ")"*sta)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    stack = deque([])
    right = 0
    for i in range(N):
        if S[i] == "(":
            stack.append(S[i])
        else:
            if stack:
                stack.pop()
            else:
                right += 1

    ans = "(" * right + S + ")" * len(stack)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

s = deque(S)

ans = []
r, l, cnt = 0, 0, 0

while s:
    q = s.popleft()
    if q == ')':
        cnt -= 1
        if cnt < 0:
            l += 1
            cnt += 1
    else:
        cnt += 1
        
if cnt > 0: r += cnt

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

Submission status: Accepted

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

for i in range(N+1):
    partial = S[:i]
    d.append(partial.count('(') - partial.count(')'))

a = -min(d)
b = d[-1]

print('(' * a + "".join(S) + ')' * (b + a))

Submission status: Accepted

Solution code:
l = int(input())
m = input()

l = 0
r = 0
b = 0
for i in m:
    if i == ")":
        l += 1
    else:
        r += 1
    m = "(" * max(l-r,0) + m
    r += max(l-r,0)
m += ")" * max(r-l,0)
print(m)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

n = int(input())
s = input()
stack = []
ans = deque(list(s))
countl = 0
countr = 0
for c in s:
    if c == '(':
        stack.append('(')
    if c == ')':
        if stack:
            stack.pop()
        else:
            countl+=1
countr = len(stack)
for i in range(countl):
    ans.appendleft('(')
for i in range(countr):
    ans.append(')')
print(''.join(ans))

Submission status: Accepted

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

b = 0
e = 0
for s in S:
    if s == ')':
        e += 1
    else:
        b += 1
    S = '(' * max(e-b, 0) + S
    b += max(e-b, 0)
S += ')' * max(b-e, 0)
print(S)