괄호 변환

💻 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60058?language=python3

📖 문제 해결
(1) solution 함수
solution 함수 같은 경우는 문제에서 제시해 준 "올바른 괄호 문자열"로 변형하는 알고리즘에 맞춰 dfs를 이용하여 재귀적으로 구현을 하였습니다.

(2) bracket_test 함수
"올바른 괄호 문자열"인지를 판단하는 함수인 bracket_test는 stack 개념을 이용하여 구현하였습니다. 구체적으로 설명하자면 stack에 괄호를 하나씩 넣어가며 짝이 맞는 괄호가 생기면 짝이 맞는 괄호는 제거해나가면서 최종으로 stack에 아무것도 남아있지 않게 되면 "올바른 괄호 문자열"로 판단하도록 하였습니다.

(3) u와 v의 분리
"균형 잡힌 괄호 문자열"이란 '('의 개수와 ')'의 개수가 같은 괄호 문자열을 의미하고, u는 "균형 잡힌 괄호 문자열"로 더 이상 분리할 수 없는 문자열이라 문제에서 정의하였습니다. 따라서 입력된 괄호 문자열 p를 차례대로 확인하면서 '('의 개수와 ')'의 개수가 처음으로 같아질 때를 기준으로 u와 v를 나누어 주었습니다.

def bracket_test(brackets):
    
    # 균형 잡힌 괄호 문자열의 "("와 ")"의 짝이 맞는지 확인
    stack = []
    
    for idx_b, one_bracket in enumerate(brackets):
        stack.append(one_bracket)
        
        if len(stack) >= 2 and one_bracket == ')' and stack[-2] == '(':
            stack = stack[:-2]
    
    if len(stack) == 0:
        return True
    
    else:
        return False

def solution(p):
    
    # p가 올바른 문자열이거나 빈 문자열이면 그대로 반환
    if bracket_test(p) or len(p) == 0:
        return p
    
    # p를 u와 v로 나누기
    left = 0
    right = 0
    
    for idx, bracket in enumerate(p):
        
        if bracket == '(':
            left += 1
            
        elif bracket == ')':
            right += 1
        
        if left == right:
            u = p[:idx+1]
            v = p[idx+1:]
            break
            
    # 만약 u가 올바른 문자열이면 문자열 v에 대해 재귀적으로 다시 solution 함수를 수행하고
    # 반환된 값을 u 바로 뒤에 붙여서 answer 변수에 입력
    
    if bracket_test(u) :
        answer = u + solution(v)

    # 만약 u가 올바른 문자열이 아니라면 문자열 v에 대해 재귀적으로 다시 solution 함수를 수행하고
    # 반환된 값을 "("와 ")" 사이에 넣고 그 뒤에 변형한 u를 붙여 answer 변수에 입력
    # 이때, u의 변형은 앞, 뒤의 값을 자른 후 남은 괄호들을 모두 뒤집어서 수행
    
    else:
        u = u[1:-1]
        u = list(u)
        
        for i in range(len(u)):
            
            if u[i] == '(':
                u[i] = ')'
                
            else:
                u[i] = '('

        u = "".join(u)
        answer = "("+ solution(v) + ")" + u

    return answer