[Python] 프로그래머스 괄호 변환 | DFS

 

~목차~

문제

작성 코드

---

 

문제

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

프로그래머스

 

 

작성 코드

def check(par):  # 올바른 괄호 문자열인지 확인하는 함수
    stack = []
    for p in par:
        if p == '(':  
            stack.append('(') # '('라면 스택에 삽입
        elif p == ')' and stack:  
            stack.pop()  # ')'이면서 스택에 괄호가 있으면 출력
        else:  
            return False # ')'이면서 stack에 괄호가 없을 때
    return True

def swap_par(par):  # 괄호 방향 바꾸는 함수
    answer = ''
    for p in par:
        answer += '(' if p == ')' else ')'
    return answer
    
def dfs(par):
    if par == '':
        return par  # 문자열이 공백이라면 공백 반환
    
    start = par[0]
    stack = 0
    
    for i, a in enumerate(par, start=1):
        stack += 1 if a == start else -1  # 첫문자열과 같은 문자열이라면 +1 다르다면 -1
        if not stack:  # 균형잡힌 괄호 문자열 u 찾음
            u, v = par[:i], par[i:]
            break
            
    v = dfs(v)  # v에 대해서 재귀적 수행
    if check(u):  # u가 올바른 괄호 문자열이라면
        return u + v
    else:  # u가 올바른 괄호 문자열이 아니라면
        return '(' + v + ')' + swap_par(u[1:-1])
       
       
def solution(p):  # 메인 함수
    return dfs(p)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚