[프로그래머스 LV2] 괄호변환

문제

접근법

이 문제는, 접근법이라고 할게 없다. 문제에 나와 있는 방법대로 구현을 하면 되기 때문이다. 하지만, 말이 너무 복잡하고 구현 해야 하는 것도 복잡하기 때문에... 시간이 좀 걸렸다 ㅠㅠ 물론 내 능력이 아직 부족 해서 그런 것 같지만 ㅠ

3. 문자열 U가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 이 말을 토대로, 재귀함수 를 만들어서 풀면 된다.

즉, 들어오는 문자열이 빈 배열이면 빈 문자열을 반환하고, 균형 잡힌 괄호 문자열 "u"과 분리 가능한 "v" 를 나누고, "v" 를 다시 1단계 부터 수행 해서 올바른 괄호 문자열로서 반환을 해서 그 것을 u와 이어 붙히는 작업을 하는 재귀함수 를 만들면 된다.

여기서 , u 가 올바른 괄호 문자열 인지 아닌지에 따라서 과정 4를 수행 하는지 하지 않는지 갈리기 때문에, 올바른 괄호 문자열을 확인하는 함수 또한 해야한다.

그리고 재귀함수에 4번의 과정을 추가해서 만들어 주면 된다.

    def solution(p):

	# 올바른 괄호 문자열인지 아닌지 확인하는 함수
    	# "( )" 를 왼쪽 부터 검사해서 한번이라도 ")" 가 "(" 보다 먼저 나오면 False 를 반환한다.
        
        def is_perfect(p):
            perfect = 0
            p = list(p)

            for word in p:
                if word == "(":
                    perfect += 1
                else:
                    perfect -= 1

                if perfect < 0:
                    break

            return perfect >= 0

        def bracket_recrusive(w):
            w = list(w)
            is_left = 0
            is_right = 0
            u, v = [], []
				
            # 현재 들어오는 문자열을 확인해 균형 잡힌 괄호열로서 배열 2개로 나누는 반복문이다.
            # 균형잡힌 괄호열을 찾으면 바로 u를 선언하고,
            # 나머지를 v로서 선언한다.
            
            for i in range(len(w)):
                if w[i] == "(":
                    is_left += 1
                else:
                    is_right += 1

                if is_left == is_right and is_left != 0:
                    u = w[0: i + 1]
                    v = w[i + 1: len(w)]
                    break
			
            # u가 올바른 문자열이고, v가 빈 배열이면
            # 재귀함수를 하지 않아도 되기 때문에,
            # u를 반환한다
            
            if v == [] and is_perfect(u):
                return ''.join(u)
                
	    # 만약 u가 올바른 괄호열이 아니라면, 4번 과정을 진행하고,
            # v를 매개변수로 하는 재귀함수를 실행한다.
            # 그러면, v가 올바른 괄호열이 되서 반환되는데,
            # 그 것을 "4-4" 과정 처리 해주면 된다.
            
            if not is_perfect(u):
                u = u[1: len(u) - 1]
                for i in range(len(u)):
                    if u[i] == "(":
                        u[i] = ")"
                    elif u[i] ==")":
                        u[i] = "("
                v = bracket_recrusive(v)
                u = ["("] + list(v) + [")"] + list(u)
                return ''.join(u)
            else:
            
            # u가 올바른 문자열이고, v가 빈 배열이 아니라면
            # 재귀함수를 하지 않아도 되기 때문에,
            # u를 반환한다
            
                v = bracket_recrusive(v)
                return ''.join(u) + ''.join(v)

        return bracket_recrusive(p)