백준 1662번 파이썬 | 압축 (Stack)

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

---

풀이

이 문제는 내가 못하는 것중 하나인 괄호 stack 문제.... 어떻게 풀어야 되는지 방향은 알겠는데 막상 해보면 내가 짠 코드에 내가 꼬여서 잘 못풀게 된다... ㅠㅠ 그래도 깔끔한 코드로 최대한 리펙토링..

 

일단 이 문제는 '(' 전에 나오는 숫자만큼 '(' ')' 사이에 있는 문자 길이를 곱해주면 된다. 

재귀로 풀 수도 있다. 왜냐면 ( ) 가 중첩되기 때문에 재귀로 접근해도 된다. 하지만 나는 재귀로 안풀었다..

 

일단 '('랑 ')'가 아니면 길이는 1씩 증가하고 그 숫자를 temp에 저장해둔다.

그러다가 '('를 만나게 되면 stack에 바로 전의 값( 곱해주어야 하는 값 = temp) 와 temp 전까지의 길이를 저장한다.

그리고 length는 다시 0으로 초기화 시켜줘야 하는데 또 다른 '('가 나올수도 있기 때문에 길이를 초기화 해준다.

 

다시 length를 쌓아주다가 ')'를 만나게 되면 stack에서 꺼내서 (가장 최근 '(' ')' 관련 값들이 뽑힘) 곱해야 하는 값과 괄호 사이의 길이를 곱해주고 그 이전 괄호와 지금 곱해줘야 하는 값이 나오기 전까지의 길이를 더해준다. 이걸 반복해주면 됨.

# 1662
# 압축
s = input()
stack = []
length = 0
temp = ''
for c in s:
    if c.isdigit():
        length += 1
        temp = c
    elif c == '(':
        # temp는 곱해야 하는 수, length-1 은 ( 를 만나기 전까지의 전체 길이
        stack.append((temp, length - 1))

        length = 0 # 초기화. ( )가 또 나올 수도 있기 때문에
    else:
        # ) 일때, multi 곱해야 되는 수, preL '('부터 multi 전까지의 길이, length는 ( ) 사이에 있는 문자 길이 
        multi, preL = stack.pop()

        length = (int(multi) * length) + preL


print(length)

 

예를 들어서 s가 3413(13(3)) 이라고 하자

그러면 첫번째 ( 가 나오는 지점에서 temp는 3, length는 3이다. 

두번째 ( 나오는 시점에 temp는 3 length는 1이다.

첫번째 ) 가 나오는 시점에서 stack을 보면 가장 최근 괄호값인 (3,1)이 뽑히게 된다.

여기서 곱해줘야 하는 multi값 3 * 괄호 사이의 문자 길이 (1) 을 해주고 첫번째 괄호 ( 부터 두번째 곱해줘야 하는 값 3 전까지의 길이 (1) 을 더해준다. 그러면 결국에는 3413(1333) 이 됨. 다시 ) 를 만나니까 위에식처럼 해주면 15가 나온다.