[Python] 2020 KAKAO BLIND RECRUITMENT - 괄호변환

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

[ 알고리즘 ]

구현

 

[문제 접근]

이 문제는 재귀함수와, 문제를 잘 이해하느냐가 관건인 문제인 것 같다.

올바른 괄호 문자열인지 아닌지를 판별하여 올바른 문자열일때와 올바른 문자열이 아닐 때로 나누어준다

 

[코드]

# u,v로 분리
# u 가 올바른 인지 아닌지
from collections import deque

def right(u): # 올바른 인지 아닌지
    que=deque()
    
    for i in u:
        if i=='(':
            que.append(i)
        else:
            if len(que)!=0:
                que.pop()
            
    if len(que)==0: # 올바른임
        return True
    else:
        return False

    
def devide(w): #u와 v로 나누기
    que_left=deque() # ( 담는 que
    que_right=deque() # ) 담는 que
    u=''
    v=''
    
    for i in range(len(w)):
        if w[i]=='(':
            que_left.append(w[i])
        else:
            que_right.append(w[i])
        
        if len(que_left)==len(que_right):
            u=w[0:i+1]
            
            if i+1==len(w):
                v=''
            else:
                v=w[i+1:]
            break
            
    return u,v

def Reverse(w): # 뒤집어주기
    s=''
    
    for i in w:
        if i=='(':
            s+=')'
        else:
            s+='('
    
    return s
    

def solution(w):
    answer = ''
    
    # 주어진 w가 올바른이라면
    if right(w)==True or w=='':
        return w
    
    u,v=devide(w)
    
    if right(u)==True: # 올바른이라면
        s=solution(v)
        
        return u+s
        
    else: #올바른이 아님
        string="("
        string+=solution(v)
        string+=")"
        
        u=u[1:-1]
        u=Reverse(u)
        
        string+=u
        
        return string