괄호 변환

p.346

 

DFS/BFS 문제라기 보단 구현 문제에 가까움

 

def divide(p):
  count=0
  for i in range(len(p)):
    if p[i]=='(':
      count+=1
    else:
      count-=1
    if count == 0:
      return i

def iscorrect(u):
  count = 0
  for i in range(len(u)):
    if u[i]==')':
      if count == 0:
        return False
      count -= 1
    else:
      count +=1
  return True

def solution(p):
    answer = ''
    if p==answer:
      return answer
    
    index=divide(p)
    u,v=p[:index+1],p[index+1:]

    if iscorrect(u) == True:
      answer=u+solution(v)
    else:
      answer='('
      answer+=solution(v)
      answer+=')'
      for i in range(1,len(u)-1):
        if u[i]=='(':
          answer+=')'
        else:
          answer+='('
    return answer

p=input()

a=solution(p)
print(a)