[프로그래머스] 괄호 변환 (Python)

풀이

주어진 조건을 완벽히 구현할 수 있는지가 문제의 포인트라고 생각한다. 함수안에 같은 함수가 들어있는 재귀적인 구조와 '올바른 문자열'을 판단할 때 Stack을 사용하는 로직을 이해한다면 문제를 구현하는데 어렵지 않을 것이라고 생각한다.

※ TIP

• 문자열 일치 문제는 문자열의 끝에 집중하는 Stack을 활용하여 푼다.
• 특정 조건을 만족하는 문자열 길이 문제는 표를 만들어서 DP로 푼다.
• 찾고자 하는 문자열의 접두사와 접미사가 일치한다면 KMP 알고리즘으로 푼다.

코드

def divide(word):
    open_bracket, close_bracket = 0, 0
    for i in range(len(word)):
        if word[i] == '(':
            open_bracket += 1
        elif word[i] == ')':
            close_bracket += 1
        if open_bracket == close_bracket:
            return word[:i + 1], word[i + 1:]


def is_valid_string(word):
    stack = []
    for i in range(len(word)):
        if word[i] == '(':
            stack.append(word[i])
        else:
            if stack:
                stack.pop()
    if stack:
        return False
    else:
        return True


def solution(p):
    # 1번
    if not p:
        return p

    # 2번
    u, v = divide(p)

    # 3번
    if is_valid_string(u):
        return 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