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

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

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

# 2020카카오 블라인드 코딩테스트 2번문제이다.

# 문제 설명이 친절하지 않은데.. 문제 설명을 잘 읽고 따라가면 크게 어렵지 않게 풀 수 있다.

 

1. 우선 '균형잡힌 괄호 문자열'과 '올바른 괄호 문자열' 두가지가 있는데,

   '균형잡힌 괄호 문자열'은 단순히 ')'의 개수와 '('의 개수가 같으면 된다.

   '올바른 괄호 문자열'은 우리가 처음 스택을 배울때 푸는 문제에서처럼 괄호의 짝이 맞으면 된다.

      * (괄호의 짝이 맞으려면 ')'의 개수와 '('의 개수는 당연히 같아야하므로 올바른 괄호 문자열은

           균형잡힌 괄호 문자열'이다)

 

2. 문자열 p를 두 "균형잡힌 괄호 문자열" u, v로 분리해야 한다.

   일단 "균형잡힌 괄호 문자열"이 되려면 ')'와 '('의 개수가 같아야 하므로 u와 v는 모두 짝수길이를 가진다.

    (p역시 길이가 2이상 1000이하인 "짝수"라고 주어져있다.)

   

   따라서, 나는 33번째 줄처럼 2개부터 len(p)까지 짝수개 단위로 p를 자르면서 진행을 했다.

     * 앞에서부터 2개 단위로 자르면, 최소문자열 길이인 2일 때도 앞에 두 괄호를 u로 하고

       v가 빈 문자열이 되어 반례가 없고, 만약 u가 '균형잡힌 괄호 문자열'로 더 분리가 가능하다면

       이미 앞에서 잘리기 때문에 반례가 없다.

       (u가 ')( )('일 때 이미 앞에 2개가 '균형잡힌 괄호 문자열'이기 때문에 그 전에 u가 ')('로 잘린다.) 

 

3. u를 p[ : i], v를 p[i : ]로 설정하고 u에서 (의 개수와 )의 개수를 count해준다.

   두 괄호의 개수가 같으면 u는 현재 '균형잡힌 괄호 문자열'이므로 3번과정으로 넘어간다.

   check(u)함수를 실행해 u가 '올바른 괄호 문자열'인지 확인해준다.

   check(u)가 참이면 3-1로 넘어가 v에 대해 1단계부터 다시 수행한다.

       1단계부터 다시 수행하는 것은 그냥 solution(v)를 재귀적으로 실행하면 된다.

       그리고 answer에 u를 더해주고 solution(v)를 더해주면 된다.

   check(u)가 거짓이면 4번으로 넘어간다.

 

4. u가 '올바른 괄호 문자열'이 아닐때는 4-1부터 4-5까지 과정을 거치면 된다.

   4-1. new_s에 '('를 붙인다.

   4-2. v에 대해 1단계부터 재귀적으로 수행한결과 solution(v) 를 new_s에 이어 붙인다.

   4-3. new_s에 ')'를 붙인다.

   4-4. u의 첫번째와 마지막 문자를 제거하고 (u[1 : -1]), 나머지 문자열의 괄호 방향을

          뒤집어서 (change(uu)) new_s 뒤에 붙이고 생성된 문자열을 반환한다.

 

def solution(p):
	# 올바른 괄호 문자열인지 판단하는 함수
    def check(s):
        stack = []
        for i in s:
            if i == '(':
                stack.append(i)
            else:
                if not stack:
                    return False
                else:
                    stack.pop()
        
        return not stack
    
    # 문자열의 괄호 방향을 뒤집어서 반환해주는 함수
    def change(s):
        tmp = ''
        for i in s:
            if i == ')':
                tmp += '('
            else:
                tmp += ')'
        return tmp
    
    # p가 이미 올바른 문자열이면 그대로 return, 빈 문자열이면 그대로 return
    if check(p):
        return p
    if len(p) == 0:
        return ''

    answer = ''
    mx = len(p)
    # 짝수개 단위로 u를 끊어보자
    for i in range(2, mx+1, 2):
        u = p[ :i]
        v = p[i: ]
        
        if u.count(')') == u.count('('):
            if check(u):
                # 균형잡힌 문자열이고 올바른 문자열이면 v 1단계부터 수행
                answer += u
                answer += solution(v)
            else:
                new_s = '(' + solution(v) + ')'
                uu = u[1:-1]
                new_s += change(uu)
                answer += new_s
            return answer

    return answer

(프로그래머스 level: 2)

 

# 4-4번 과정에서 "나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다" 를 처음에 잘못 보고

   그냥 나머지 문자열을 뒤집어서 uu[ : :-1]로 반환해줘서 틀렸다.

   (테스트케이스 13 ~ 21번까지 쫙 틀리면 이걸 잘못 보고 푼 것이다)