[DFS/BFS] 괄호변환

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40분 + a

1. 문제 설명

- 괄호( '( )')가 주어졌을 때, 이것이 서로 짝이 맞는지 확인하고 맞지 않는다면 짝을 맞출 수 있도록 재귀적으로 코드를 만드는 문제

2. 접근 방식

- DFS라는 것은 문제 설명으로 알 수 있었다.
- 하지만 DFS보다는 구현과 관련된 문제라는 생각이 들었다.

- 그래서 문제를 푸는데 꽤나 힘들었고, '완전한 문자열'로 만드는 키 아이디어를 생각하지 못해서 결국 해답을 봐버렸다.

- 완전한 문자열로 만드는 경우 해답에서는 균형잡힌 문자열을 입력으로 받아서 균형이 안맞는 경우가 생기면 False를 리턴하는 함수를 통해 구현을 했다. 해당 키 아이디어를 이해한 순간 나머지 코드는 자연스럽게 풀 수 있었다. 

3. 코드

# 균형잡힌 괄호 문자열의 인덱스 반환
# 여기까지는 구현했었다.
def balaced_index(p):
    count = 0 # 왼쪽 괄호의 개수
    for i in range(len(p)):
        if p[i] == "()":
            count+=1
        else:
            count -=1
        if count == 0:
            return i 
        
# 이거를 구현하지 못했다. 
# 균형잡힌 괄호 문자열만 들어오기 때문에 중간에 0이 되면 안 된다.
# 예를 들어 (()))( 이 경우 도중에 0이 되어 버린다. 그러면 완전한 문자열이 아니게 된다.
def check_proper(p):
    count = 0
    for i in p:
        if i == "(":
            count+=1
        else:
            if count == 0:
                return False
            count -=1
    return True

# 주어지는 input의 개수는 균형잡힌 괄호 문자열이다.
# 균형잡힌 괄호 문자열인지 확인하는 함수 필요
from collections import deque
def solution(p):
    answer = ""
    if p == "":
        return answer
    i = balanced_index(p)
    u, v = p[:i+1], p[i+1:]
    if check_proper(u):
        answer = u+solution(v)
        return answer
    else:
        answer += "("
        answer += solution(v)
        answer += ")"
        for i in u[1: -1]:
            if i =="(":
                answer += ")"
            else:
                answer += "("
        return answer

4. 코멘트

- 확실한 키 아이디어를 생각하기까지는 많은 경험이 필요해보인다.