[Lv2]괄호 변환(python)

1. 문제

 

2. 구현 과정

- 정말.... 이 문제만 보면 그렇게 졸음이 와서(?) 문제 이해하는데 오래 걸렸다.. 문제 이해하는 데 대부분의 시간을 소요한 것 같다.

 

- 구현 방법은 이미 문제에서 다 정의해줬고, 특별한 알고리즘을 사용하는게 아니라 재귀 함수를 만드는 거라 특정 알고리즘에 대해 고민할 필요는 없었다. 문제를 제대로 이해하는 게 핵심인 것 같다.

 

- 구현의 흐름은 문제에서 정의했지만 중요한 건 "왜?" 저렇게 구현해야 하는지 인데, 큰 흐름은 다음과 같다.

 

   1) 문자열을 균형잡힌 문자열( U ) 와 나머지 문자열 ( V ) 로 나눔

 

   2) U가 올바른 문자열이 아니라면, 'U'의 시작 문자는 ')', 마지막 문자는 '('일 것이다!

    균형 잡힌 문자열이면서 올바른 문자열이 아니다 =  '('와 ')'의 개수는 같지만 ( )모양이 만들어 지지 않는다는 의미.  즉, 무조건 ')'으로 시작을 해야 하고, '('으로 끝나야 함. '('으로 시작을 한다면 언젠가 개수를 맞추기 위해 ')'이 있어야 하는데, 그렇게 되면 올바른 문자열이 생성되므로 조건에 맞지 않는다. 마찬가지로 ')'로 끝이 난다면 올바른 문자열이 생성되므로 ')' '('쌍이어야 한다.

    =>  올바른 문자열이 아닐 경우, 첫번째와 마지막 문자를 제거함으로써 올바르지 않은 문자열의 문제 부분을 삭제 후, 방향을 뒤집어 주면 올바른 문자열이 됨

 

    3) 위 방식을 통해 올바른 문자열로 바꿔가면서 최종적으로 전체 문자열이 올바른 문자열이 되도록 한다.

 

- 올바른 괄호 문자열 판단 방법은 stack을 이용.  '('일 때 append, ')'일 때 pop 해서 문자열이 끝났을 때 stack 내 아무것도 없으면 올바른 괄호이다.

3. 새로 안 것 & 실수한 것

1) python에서의 stack : append(), pop()

 

2) list의 인덱스로 마이너스(-)값을 부여 가능. -1이면 가장 마지막 값!

   ex) array[1:-1] : array의 2번째 ~~ 마지막에서 두번째 값까지만 출력  / 배열의 양 끝값 지우고 출력 

 

3) 배열이 비었는지 확인 법 : not array == True

 

4) 문자 배열을 문자열로 합치는 법 : "".join(배열)

 

5) 특정 인덱스의 배열 값 삭제하는 법 : del array[i]

 

6) 문제를 이해하기 어려워서 예제를 보고 이해하다보니 나도 모르는 새 U = '가장 왼쪽 2개 문자열'이라고 생각했다. 예제 3개가 우연히 왼쪽 두개에서 균형잡힌 괄호 문자열이어서 2개로 쪼개진 거였다... 이런 함정(?)에 낚이지 말고 문제가 어려워 보여도! 이해가 잘 안되어도! 날려읽지 말자

 

7) 문제에서 "균형 잡힌 괄호 문자열" 과 "올바른 괄호 문자열" 두 가지 개념에 대해 정의를 했다. 문제에서 두 가지 이상(그것도 둘이 비슷하면)의 개념을 정의했다면, 두 개념의 차이점에 대해 계속 인지하고 주의 깊게 살펴봐야 한다! (난 그러지 못해서 오래 해맸다.)

 

 

4. 코드

# 올바른 괄호 문자열 확인 
def is_correct(str):  
    stack = []
    for s in str:
        if s == '(':
            stack.append(s)
        elif stack: #')'인데 스택에 값이 있으면 
             stack.pop()
        else:
            return False
    return not stack 


# u와 v로 분리
def divideStr(str):
    cnt = 0
    u = ""
    for i in str:
        u += i
        if i == '(':
            cnt += 1
        else:
            cnt -= 1
        
        if cnt == 0:
            return [u, str[len(u):]]


def solution(p):
    answer = ''
    
    # 1번 수행 
    if (p == '') | (is_correct(p) == True): 
        return p
    
    # 2번 수행 
    u,v = (divideStr(p))
    
    # 3번 수행
    if is_correct(u):
        answer = u + solution(v)
    
    #4번 수행
    else:
        u = u[1:-1] 
        u = u.replace('(','a')
        u = u.replace(')','b')
        u = u.replace('a',')')
        u = u.replace('b','(')
        answer = '(' + solution(v) + ')' + u

    return answer