프로그래머스 [Lv. 2] 괄호 변환 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

answer = ""
def solution(p):
    global answer
    def isValid(uvp):
        stack = []
        lenUVP = len(uvp)
        for i in range(lenUVP):
            cv = uvp[i]
            if cv == "(":
                stack.append(cv)
            else:
                if stack:
                    if stack[-1] == "(":
                        stack.pop()
                    else:
                        stack.append(cv)
                else:
                    return False
        if stack:
            return False
        else:
            return True
                        
    
    def checkUV(w):
        if not w:
            return ""
        lenW = len(w)
        idx = 0
        balance = 0
        for s in range(lenW):
            if w[s] == "(":
                balance += 1
            else:
                balance -= 1
            if balance == 0:
                idx = s + 1
                break
        u = w[:idx]
        v = w[idx:]
        if isValid(u):
            return u + checkUV(v)
        else:
            tmp = "("
            tmp += checkUV(v)
            tmp += ")"
            for s in u[1:len(u)-1]:
                if s == '(':
                    tmp += ')'
                else:
                    tmp += '('
            return tmp
    answer = checkUV(p)
    return answer

풀이 방법

1. 핵심은 u와 v를 나누는 방법과 괄호가 유효한지 확인하는 방법이다.
2.  u와 v를 나눌 때 밸런스만 맞으면 u로 나머지는 v로 한다.
3. u의 괄호가 유효하든 아니든 v는 재귀를 돌리고 u가 유효하지 않으면 괄호의 방향을 돌린다.
4. 마지막으로 반환된 값들이 합쳐지면서 나온 answer를 반환하면 끝!

느낀점

• 이런 문제 나오면 틀릴 것 같아서 다시 풀어보면 좋겠다고 생각한 문제다.