[프로그래머스-파이썬] 연습문제(LV2) : 괄호 변환

<문제출처>

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

프로그래머스

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

 

<고민 끄적끄적>

문제에서 요구하는 재귀함수를 그대로 구현만 하면 되는 문제이다. 문제에서 하란대로 그대로 구현하자.
"올바른 괄호 문자열"인지는 스택 자료구조를 이용해서 판단하면 된다.

 

 

최종코드

'''
균형 -> 올바른으로 변환하기
'''

from collections import deque

def correct(s):
    stack = deque()
    for x in s:
        if len(stack) == 0:
            stack.append(x)
            continue
        
        if stack[-1] == '(' and x == ')':
            stack.pop()
        else:
            stack.append(x)
    
    if len(stack) == 0:
        return True
    else:
        return False
    

def recur(p):
    if p == '':
        return ''
    
    # u, v로 나누기
    cnt = [0, 0]
    for x in p:
        if x == ')':
            cnt[0] += 1
        elif x == '(':
            cnt[1] += 1
            
        if cnt[0] == cnt[1]:
            break
    u = p[:2*cnt[0]]
    v = p[2*cnt[0]:]
     
    # 3, 3-1
    if correct(u):
        return u + recur(v)
    
    else:
        new = '(' + recur(v) + ')'
        k = ''
        for x in u[1:-1]:
            if x == ')':
                k += '('
            else:
                k += ')'
        
        return new + k
    

def solution(p):
    return recur(p)