[이코테] DFS/BFS - 괄호 변환

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

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

사고과정

• 문제를 이해하는게 너무 어려웠다. 그래서 프로그래머스 질문 사이트에서 보니 나만 그런게 아니라 다른 분들의 질문 답변을 통해서 문제를 이해했다. 그리고 재귀함수를 어떻게 구현해야 할지 몰라서 고민하다가 풀이를 보았다. 재귀함수가 너무 약한 듯 하다.. 어떻게 하지..?

풀이(스스로 못 푼 풀이)

# 균형잡힌 괄호 문자열이 어디 인덱스까지 인지 알려주는 함수
def balanced_index(p):
    count = 0
    for i in range(len(p)):
        if p[i] == '(':
            count += 1
        else:
            count -= 1
        if count == 0:
            return i
    
# 균형잡힌 괄호 문자열이 올바른 괄호 문자열인지 체크하는 함수
def check_proper(p):
    count = 0
    for i in p:
        if i == '(':
            count += 1
        else:
            if count == 0: # count가 0인 된 상태에서 )가 먼저 나오면 쌍 안맞음!
                return False
            count -= 1
    return True

def solution(p):
    answer = ''
    if p == '':
        return answer
    index = balanced_index(p)
    u = p[:index+1]
    v = p[index+1:]
    # 균형잡힌 괄호문자열이 올바른 괄호문자열이라면!
    if check_proper(u):
        answer = u + solution(v)
    else:
        answer = '('
        answer += solution(v)
        answer += ')'
        u = list(u[1:-1])
        for i in range(len(u)):
            if u[i] == '(':
                u[i] = ')'
            else:
                u[i] = '('
        answer += ''.join(u)
    return answer