[Level 2 프로그래머스] 카카오 기출, 2020 KAKAO BLIND RECRUITMENT - 괄호 변환(Python 파이썬)

 

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

카카오 기출문제이다. 괄호 관련된 문제가 약해서 풀어보려는데, 역시나 실수가 많이 나왔다.

 

막상 다 풀고보면 문제에 있는 말 그대로를 구현하는 것인데.. 아직 구현력이 부족한 듯 하다.

 

 

 

문제 조건

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   3. ')'를 다시 붙입니다.
   4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   5. 생성된 문자열을 반환합니다.

 

실수했던 부분

 

올바른 괄호를 판단하고 u, v로 나누는 것 까지는 다 했는데, 1단계부터 재귀적으로 실행하는 부분을 어떻게 해야할 지 몰랐다.

 

프로그래머스는 solution 함수로 주어지는데, solution 자체를 재귀로 활용할 아이디어가 떠오르지 않았었다.

 

 

또한 4-4번의 조건을 잘못봐서 계속 틀렸었다. 괄호의 방향을 뒤집는 것인데 괄호의 순서를 뒤집었었다.

 

다시 말해, ( ( ) ) )이라면 ) ) ( ( (이렇게 괄호 자체가 뒤집어져야 하는데, 괄호의 순서를 뒤집다보니 ) ) ) ( ( 이런 결과가 나와서 계속 틀렸었다.

 

 

 

소스코드

 

def isCorrect(s):
    _list = []
    for i in s:
        if i == '(':
            _list.append('(')
        else:
            if not _list:
                return False
            _list.pop()
    return True


def isBalanced(s):    
    left = 0
    right = 0
    for i in s:
        if i == '(':
            left += 1
        else:
            right += 1
    if left == right:
        return True
    else:
        return False

def doSplit(s):
    y = ''
    x = ''
    for idx, val in enumerate(s):
        y += val
        if isBalanced(y):
            x = s[idx+1:]
            break    
    return y, x

def solution(p):    
    if isCorrect(p): 
        return p 
    # 1.입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if not p:
        return ""        
    
    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
    u, v = doSplit(p)
    
    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.     
    if isCorrect(u):        
        return u + solution(v) # 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
    
    # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
    else:      
        answer = '(' #   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.    
        answer += solution(v)  #   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        answer += ')' #   4-3. ')'를 다시 붙입니다. 
        #   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
        # u = list(u)
        # u.pop()
        # u.reverse()
        # u.pop()
        # answer += ''.join(u)
        for i in u[1:len(u) - 1]:
            if i == '(':
                answer += ')'
            else:
                answer += '('
        #   4-5. 생성된 문자열을 반환합니다.            
        return answer