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

---

문제

괄호 변환

---

문제 해설

주어진 요구사항에 따라 구현하는 문제입니다.

문자열을 두 문자열로 분리하고 이 두 문자열들을 또 분리하는 과정이 있기 때문에 재귀 형태로 구현했습니다.

일단 균형잡힌 문자열과 올바른 문자열에 대해 정확히 이해하면 균형잡힌 문자열은 )로 시작해도 상관 없으나 개수가 맞아야 하고, u는 더이상 분리할 수 없는 균형잡힌 문자열이기 때문에 (와)의 개수가 맞으면 바로 종료해야 합니다.

올바른 문자열은 위에서 구한 u가 (로만 시작하면 반드시 올바른 문자열에 해당합니다. 왜냐하면 u는 이미 더이상 분리할 수 없는 균형잡힌 문자열 이라는 전제를 깔고 있기 때문입니다.

---

풀이 코드

# 두 균형잡힌 괄호 문자열로 분리
def divide(string):
    if string == "":
        return ""
    answer = ""
    top = 0
    u = v = ""
    for i in range(len(string)):
        top = top + 1 if string[i] == "(" else top - 1
        u += string[i]
        if top == 0:
            v = string[i + 1 :]
            break
    # 만약 u가 올바른 괄호 문자열이라면
    if u[0] == "(":
        answer += u + divide(v)
    else:
        answer += "(" + divide(v) + ")"
        for s in u[1:-1]:
            answer += "(" if s == ")" else ")"
    return answer


def solution(p):
    answer = ""
    answer += divide(p)
    return answer