[Python/프로그래머스/2020 KAKAO BLIND RECRUITMENT] 괄호 변환

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

프로그래머스

 

 

 

---

문제 풀이 방법

 

solution(p)를 해결하기 위해서 3개의 함수를 정의했다.

1. check(array) : array(=리스트)를 입력받아서 올바른 괄호 문자인지 아닌지 여부(T/F)를 return 한다.
2. split_uv(array) : array(=리스트)를 입력받아서 u와 v를 분리해준다. u와 v를 return 한다.
3. dfs(array) : array(=리스트)를 입력받아서 올바른 괄호 문자로 만들어준다. 올바른 괄호 문자를 return한다.

 

 

 

dfs 함수 구현 방법

 

 

---

Code

# p: 균형잡힌 괄호 문자열이다. '('와 ')' 개수가 동일하다.
# p가 올바른 괄호 문자열인지 판별
def check(array):
    left = 0
    right = 0
    anv = True
    for i in range(len(array)):
        if array[i] == '(': left += 1
        else: right += 1
        # 올바른 괄호 문자열이 아닌 경우
        if left < right: anv = False; break
    return anv
 
 
# 올바른 괄호 문자열이 아니라면, u와 v로 나눠주자
def split_uv(array):
    left = 0
    right = 0
    for i in range(len(array)):
        if array[i] == '(': left += 1
        else: right += 1
        # '('와 ')'개수가 같을때까지
        if left == right:
            u = array[:i+1]
            v = array[i+1:]
            break
    return u,v
 
 
def dfs(array):
    if not array: return [] # 빈 리스트 반환
    if not check(array):    # array가 올바르지 않으면, u와 v로 나눔
        u, v = split_uv(array)
        if check(u): # u가 올바르면 v에 대해서 처리
            return u + dfs(v)
        else:        # u가 올바르지 않다면
            empty_list = ['('] + dfs(v) + [')']
            u = u[1:-1]
            for i in range(len(u)):
                if u[i] == '(': u[i] = ')'
                else: u[i] = '('
            return empty_list + u
    return array
 
 
def solution(p):
    p = list(p)
    anv = dfs(p)
    return ''.join(anv)