괄호 변환 (Python)

https://programmers.co.kr/learn/courses/30/lessons/60058

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

---

문제 해결을 위한 과정

이 문제의 경우 재귀를 얼마나 잘 사용할 수 있느냐 그리고 구현 알고리즘을 얼마나 잘 사용할 수 있느냐가 중요한 문제였다고 생각합니다. 문제의 조건을 그대로 꼼꼼하게 코드로 옮기기만 한다면 쉽게 정답을 맞을 수 있는 문제였습니다.

먼저 재귀의 탈출 조건으로 빈 문자열이 들어온 경우 그대로 빈 문자열을 반환하는 것 과

문자열 W를 u, v로 분류하는 것입니다.

이 문제의 경우 균형 잡힌 괄호 문자열을 만드는 함수, 올바른 괄호 문자열인지 확인 하는 함수, solution함수 총 3개의 함수로 구분하여 코드를 작성하면 쉬운 문제였습니다.

균형 잡힌 괄호 문자열로 더이상 분류를 할 수 없게 최소한의 길이를 가진 u를 만들어 낼 수 있도록 균형잡인 괄호 문자열을 만드는 함수 balance함수에서 앞에서부터 몇번째 인덱스에서 최소한의 길이를 가진 균형잡인 괄호 문자열이 만들어지는지를 반환을 해주면 그 반환된 인덱스를 기준으로 리스트를 인덱싱 하여 u와 v를 구분할 수 있습니다.

그 후 u를 다시 올바른 괄호 문자열인지 확인하는 함수 correct를 통해 확인한 후 이 결과에 따라 문제의 조건처럼 재귀를 구현하면 되는 것입니다. 이후 과정은 문제를 소스코드로 그대로 옮기는 것이기 때문에 생략합니다.

---

소스코드

def balanced(p):
    count = 0
    for i in range(len(p)):
        if p[i] == '(':
            count += 1
        elif p[i] == ')':
            count -= 1
        if count == 0:
            return i
        
def correct(u):
    count = 0
    for i in range(len(u)):
        if u[i] == '(':
            count += 1
        elif u[i] == ')':
            count -= 1
        if count < 0:
            return False
    return True
 
def solution(p):
    if p == '':
        return p
    answer = ''
    
    index = balanced(p)
    u = p[:index + 1]
    v = p[index + 1:]
    
    if correct(u):
        return (u + solution(v))
    else:
        answer += '('
        answer += solution(v)
        answer += ')'
        u = list(u)
        u = u[1:-1]
        for i in range(len(u)):
            if u[i] == '(':
                u[i] = ')'
            else:
                u[i] = '('
        answer += ''.join(u)
        return answer