[백준] 1662 - 압축

1. 문제

1662번: 압축

2. 개요

스택 활용 문제.

K(Q)형식으로 압축된 문자열의 압축을 해제했을 때, 그 길이를 구하는 문제.

(K는 한자리 정수, Q는 문자열)

3. 코드 및 추가내용

import sys

s = sys.stdin.readline().rstrip()

stk = []

for char in s:
    if char != ')':
        stk.append(char)

    else:
        num2 = ''
        while stk[-1] != '(':
            num2 += stk.pop()
        
        stk.pop()
        num1 = int(stk.pop())
        tmp = num1 * num2[::-1]

        stk += [tmp]

print(len(''.join(stk)))

첫 시도. 답은 잘 나오는데 메모리 초과.

압축해제한 문자열이 길어지는 … 9(9(9(9(Q)))) 같은 경우에 메모리 초과가 나는 듯 싶다.

import sys

s = sys.stdin.readline().rstrip()

stk = []

for char in s:
    if char != ')':
        stk.append(char)

    else:
        num2 = 0
        while stk[-1] != '(':
            k = stk.pop()
            if str(type(k)) == "<class 'str'>":
                num2 += 1
            else:
                num2 += k
        
        stk.pop()
        num1 = int(stk.pop())
        tmp = num1 * num2

        stk += [tmp]

ans = 0
for i in stk:
    if str(type(i)) == "<class 'str'>":
        ans += 1
    else:
        ans += i

print(ans)

해서 압축해제한 문자열을 그대로 넣기보단 문자열의 길이를 넣어 계산하는 방식으로 바꿨다.

str과 int 서로간의 연산이 불가능하므로 타입을 항상 확인해주며 진행하면 해결.