[프로그래머스] 파이썬 _ 괄호변환 ( 2020 KAKAO BLIND)

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

코딩테스트 연습 - 괄호 변환

 

문제유형 : 구현, 재귀 

 

문제풀이  :

 

• 문제에서 주어진 로직을 그대로 구현할 수 있느냐 없느냐
• 재귀함수를 잘 이해해야한다.

 

• 괄호가 짝이 맞는지 체크할때는 스택을 이용한다.
  • 괄호가 열릴때마다 스택에 넣고 괄호가 닫힐때마다 스택에서 빼면된다.
  • 이때 닫힌 괄호가 나와서 스택에서 하나 빼려할때 스택이 비었다면, 즉 열리지도 않았는데 닫히려고한다는것이므로 짝 안맞음 
  • 이 문제에서는 괄호의 개수는 맞다는 조건이 있었지만, 이게 없다면 스택에 열린괄호가 남아있을때도 False를 리턴하도록 해야한다. (닫힌괄호가 부족한경우)

 

재귀함수 넘모 어렵다,, 재귀함수를 자꾸 따라들어가서 생각하려 하지말고 어떻게 나올것이다 하는 믿음을 가지고

어떤 부분이 반복되는지 ( 큰문제가 어떤 반복문제로 나뉘어지는지) 를 생각해야한다.

 

정답코드:

def solution(p):
    # 1번
    if not p:
        return ""

    # 2번
    u,v = seperate(p)

    # 3번
    if isBalanced(u):
        #seperate(v)
        # 3-1
        return u + solution(v) # 이부분을 이해하는것이 어려웠다.
    # 4번
    else:
        # 4-1
        answer = '('
        # 4-2
        answer += solution(v)
        # 4-3
        answer += ')'

        # 4-4
        for i in u[1:-1]:
            if i == '(':
                answer += ')'
            else:
                answer += '('
        # 4-5
        return answer

# 문자열을 u와 v로 분리하는 함수
def seperate(p):
    left_count = 0
    right_count = 0
    for idx, i in enumerate(p):
        if i == '(':
            left_count += 1
        elif i == ')':
            right_count += 1
        # 더이상 나눠질 수 없는 올바른 괄호문자열 찾음
        if left_count == right_count:
            return p[:idx + 1], p[idx + 1:] # u,v


def isBalanced(u):
    stack = []

    for i in u:
        if i == '(':
            stack.append(i)
        else:
            if not stack:
                return False
            stack.pop()
    return True