[프로그래머스]괄호 변환(level2)

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

프로그래머스

풀이

카카오 2020 블라인드 채용 문제 중 하나이다. 레벨2와 레벨3를 중심적으로 보고 있는데, 난이도가 꽤 있어서 쉽지 않다. 이 문제는 재귀 문제였는데, solution 함수 자체를 재귀하는 것은 처음이어서 조금 당황하기는 했다. 문제에서 친절하게 올바른 괄호를 만드는 법을 알려주었기에, 그대로 구현하면 된다. 간단히 매커니즘을 얘기하자면 한 문자열 p에 대하여 이 문자열이 올바른 괄호 문자열인지를 판별하는 verify함수와, u, v로 나눠주는 함수 seperate을 선언하고 구현하였다. 그 다음 u, v에 대하여 만약 u가 올바른 문자열이면 v를 패러미터로 재귀를 해주면 되고, 만약 올바르지 않다면 설명에 나온대로 (를 붙이고 v에 대하여 solution함수를 재귀한 값을 더해주고 )로 닫아준 후, u에 남은 값의 앞 뒤를 빼주고 괄호의 반대를 넣어주면 된다. 이게 어떻게 올바른 괄호를 만드는지는 모르겠지만, 설명한대로 구현했더니 문제 없이 작동한다.

def verify(s):
    stack = []
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(1)
        else:
            if not stack:
                return False
            stack.pop()
    if stack:
        return False
    else:
        return True

def seperate(s):
    opening = 0
    closing= 0
    u, v = '', ''
    if s[0] == '(':
        opening += 1
    else:
        closing += 1
    u += s[0]
    for i in range(1, len(s)):
        if s[i] =='(':
            opening += 1
        else:
            closing += 1
        u += s[i]
        if opening == closing:
            if i != len(s)-1:
                v = s[i+1:]
            return u, v
def solution(p):
    answer = ''
    if not p:
        return p
    u, v = seperate(p)
    #print(u, v, verify(u))
    if verify(p):
        return p
    if verify(u):
        answer += u
        if not verify(v):
            answer += solution(v)
    else:
        answer += '('
        v = solution(v)
        answer += v
        answer += ')'
        u = u[1:-1]
        for i in range(len(u)):
            if u[i] == '(':
                answer += ')'
            else:
                answer += '('
    return answer