[프로그래머스] 괄호 변환 (Python) / 카카오 2020

문제

위의 규칙에 따라 입력 문자열을 "올바른 괄호 문자열"로 변환하려고 한다. 문제 링크

 

변환 과정 예시

재귀는 특정 과정(규칙)을 특정 조건까지 수행한 결과를 반환하는 문제가 대부분이다. 몇 단계만 그림을 그려보면 재귀를 이해하는데 큰 도움이 된다.

p = "()))(())" 일 때 올바른 괄호 문자열로 변화하는 과정을 그리면 위의 그림과 같다. 

 

풀이

• is_balanced() : 균형잡힌 문자열인지 확인하는 함수: ( 괄호와 ) 괄호의 개수가 같은지 확인
• is_correct() : 올바른 문자열인지 확인하는 함수 → 스택(deque 또는 list)을 사용해 이전 요소와 짝이 맞으면(반대되는 괄호이면) 이전 요소를 삭제하고, 짝이 맞지 않으면(동일한 괄호이면) 삽입한다.
• do_split() : u, v를 쪼개는 함수 → u는 균형잡힌 문자열로 다시 분리되면 안되기 때문에 처음부터 2칸씩 확인하면서 u가 균형잡힌 문자열인지 확인한다. 균형잡힌 문자열을 찾으면 바로 반환한다.
• reverse_str() : 4-4 단계에서 문자열의 괄호를 반대로 뒤집는다. → 문자열을 처음부터 끝까지 탐색하면서 괄호를 뒤집는다.
• solution() : 문제에서 주어진 올바른 괄호 문자열 변환 과정을 수행한다.
  • 빈 문자열이거나 이미 올바른 문자열은 그대로 반환한다.
  • 입력 문자열을 u, v로 쪼갠다.
  • u가 올바른 문자열이면, v에 대해서만 재귀적으로 규칙을 적용해 올바른 문자열로 만든다.
  • u가 올바른 문자열이 아니면, v에 재해 재귀적으로 수행한 결과를 () 안에 넣는다. u의 첫번째와 마지막을 버리고 괄호를 뒤집은 문자열을 뒤에 붙여 반환한다.

# 균형잡힌 괄호 문자열인지 확인
def is_balanced(s):
    if s.count('(') == s.count(')'):
        return True
    return False

# 올바른 괄호 문자열인지 확인
def is_correct(s):
    stack = []

    for i in range(len(s)):
        if not stack:
            if s[i] == ')':
                return False
            else:
                stack.append(s[i])
        elif stack[-1] == s[i]:
            stack.append(s[i])
        else:
            stack.pop()
    
    return False if stack else True

# u, v로 쪼개기
def do_split(s):
    u, v = '', ''

    for i in range(2, len(s)+1, 2):
        if is_balanced(s[:i]):
            return s[:i], s[i:]

# 괄호 뒤집기
def reverse_str(s):
    reverse = ''
    for i in range(len(s)):
        if s[i] == '(':
            reverse += ')'
        else:
            reverse += '('
    
    return reverse

def solution(p):
    answer = ''

    # 빈 문자열인 경우
    if not p or is_correct(p):
        return p

    # u, v로 쪼개기
    u, v = do_split(p)
    
    # u가 올바른 문자열인 경우
    if is_correct(u):
        answer = u + solution(v)
        
    # u가 올바른 문자열이 아닌 경우
    else:
        answer += '(' + solution(v) + ')'
        answer += reverse_str(u[1:-1])

    return answer

 

유의할 부분

• 문자열을 다룰 수 있고 재귀를 이해하면 문제에서 시키는대로 그대로 구현해 수월하게 풀 수 있는 문제였다.
• 마지막에 메인 함수가 되는 solution()에서 출력을 찍어봤는데 빈 문자열이 나와서 당황했다. ‘재귀 호출을 잘못했나?’ 라는 생각이 들었지만, 한 단계씩 출력해봤을 때 u, v로 쪼개면 문자열이 공백이 되는 것을 확인했다.
• do_split()함수에서 리스트 슬라이싱을 사용했는데, 마지막 인덱스는 포함되지 않는 것을 깜빡해 u, v가 제대로 쪼개지지 않았다. s[i:j] 에서 j 인덱스는 포함되지 않는다!!!