백준 1662 압축

재밌는 stack 자료구조를 이용한 문제 였다.
결과의 문자열 길이가 20억이 될 수 있었기 때문에 이 부분에 대한 시간을 고려해서 풀면 되겠다.

📜 문제 바로 가기 : 압축

제출코드

import sys
input = sys.stdin.readline

S = input().rstrip()

stack = []
for w in S:
    if w == ")":
        word_cnt = 0
        while 1:
            k = stack.pop()
            if k == "(":
                break
            if k[0] == "n":
                word_cnt += int(k[1:])
            else:
                word_cnt += 1
        t = int(stack.pop())
        word_cnt *= t
        stack.append("n"+str(word_cnt))
    else:
        stack.append(w)

ans = 0
for i in stack:
    if i[0] == "n":
        ans += int(i[1:])
    else:
        ans += 1

print(ans)

접근방법

문자열 길이가 20억까지도 나올 수 있었기 때문에 실제로 문자열을 일일이 스택에 넣는건 안된다.
문제에서 문자는 숫자로만 주어진다라고 했었기 때문에 별도의 문자를 추가(여기서는 "n")해서 n이 붙은 문자열 문자열이 아닌 "원래 문자열의 길이"를 나타내도록 하여 시간초과를 해결했다.

입력값으로 주어지는 문자열 길이는 최대 50이었기 때문에 곱해지는 부분의 문자열 처리만 유의해주면 될것이다.