[프로그래머스][python] 괄호 변환 - Stack, Recursion

문제

• 프로그래머스 괄호변환
• Level 2
• Link

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

 

나의 접근

와 이문제는.. 도저히 레벨 2라고 믿기 힘들 정도로 엄청 복잡한 재귀 로직을 짜는 것을 요구한다. 문제 이해가 너무 어려워서 계속 숙제처럼 미뤄두다가 오늘 도전한 문제..! 한 번에 모든 테케 통과해서 기분이 매우 좋다 ㅎㅎ

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

def solution(p):
    p = list(p)
    # 2. 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리하는 함수
    def split(lst):
        left_cnt = 0
        right_cnt = 0
        cut_idx = 0
        for i in range(len(lst)):
            if lst[i] == '(':
                left_cnt += 1
            elif lst[i] == ')':
                right_cnt += 1
            if left_cnt == right_cnt:
                cut_idx = i
                break
        u, v = lst[0: i + 1], lst[i + 1:]
        
        return (u, v)
    
    # 올바른 괄호 문자열인지 확인하는 함수
    def check(u_lst):
        lst = u_lst
        stck = []
        idx = 0
        while idx < len(lst):
            first_idx = lst[idx]
            if not stck:
                stck.append(first_idx)
            elif stck[-1] == '(' and first_idx == ')':
                stck.pop(-1)
            else:
                stck.append(first_idx)
            idx += 1
        if stck:
            return False
        else:
            return True  
    
    # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행하는 함수. 
    # 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
    def convert(string_val):
        string_val.pop(0)
        string_val.pop(-1)
        if not string_val:
            return []
        else:
            for i in range(len(string_val)):
                if string_val[i] == '(':
                    string_val[i] = ')'
                else:
                    string_val[i] = '('
            return string_val
        
    def change(w):
        # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
        if len(w) == 0:
            return []
        # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
        # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
        u, v = split(w)
        # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
        if check(u):
            return u + change(v)
        
        # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
        else:
            # 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
            new_u = convert(u)
            # 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
            # 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
            # 4-3. ')'를 다시 붙입니다. 
            return ['('] + change(v) + [')'] + new_u
            
    return (''.join(change(p)))

 

사실 주어진 로직을 그대로 따라하면 되는 문제인데, 중간 중간 구현해야하는 것들이 많아 복잡하게 느껴질 수 있다. 

1. 우선 가장 주가 되는 change함수를 기준으로 재귀 로직을 먼저 작성하고, 그 안에 들어가야 할 외부 함수들을 pseudocode로 작성해주었다.
2. 올바른 괄호 문자열인 "(()())()"에 대해서 재귀 로직과 check 함수가 올바르게 돌아가는지 체크했다.
3. convert 함수를 구현하고, 균형잡힌 괄호 문자열에 대한 재귀 로직을 작성했다.
4. List로 되어있는 결과를 join시켜서 스트링으로 리턴해준다.

 

결론:

요구사항이 많은 문제일수록 pseudocode를 작성해서 전체적인 흐름을 먼저 설계하고, 단계별로 디버깅 해가면서 진행하는 것이 좋다.