[Python3]프로그래머스_괄호 변환

문제출처: https://programmers.co.kr/learn/courses/30/lessons/60058

접근법

1. solve(s) -> 문자열 s가 주어지면 해당 문자열의 균형잡힌 문자열을 찾고 s -> u,v 로 나눈다. 이후 문자열 u가 올바른 괄호 문자열일 경우와 아닐 경우로 나누어 재귀함수를 실행
2. isCorrect(p) -> 문자열 p가 올바른 괄호 문자열인 지 확인한다.

• '(' 의 경우 스택에 푸쉬
• ')'의 경우 스택의 top이 '('인 경우 "()" 형태로 짝이 맞으므로 pop
• 올바른 괄호 문자열일 경우 모두 pop되어 집합 s의 크기가 0

코드

# 올바른 괄호 문자열
def isCorrect(p):
    s = []
    for bracket in p:
        if( bracket == '('):
            s.append(bracket)
        else: # ')'
            if( s and s[-1] == '(' ):
                s.pop(-1)
            else:
                s.append(bracket)
    return False if s else True

# 재귀
def solve(s):
    # 빈 문자열
    if( not s ):
        return s
    l,r = 0,0
    index = 0
    for i,bracket in enumerate(s):
        if( bracket == '(' ):
            l += 1
        else:
            r += 1
        if( r-l == 0 ):
            index = i
            break
    u = s[:index+1]
    v = s[index+1:]

    if( isCorrect(u) ):
        return u + solve(v)
    else:
        new_u = ""
        for bracket in u[1:-1]:
            new_u += '(' if bracket == ')' else ')'
        return "(" + solve(v) + ")" + new_u
    
def solution(p):
    return solve(p)