[백준 1662] 압축(Python)

1. 아이디어

문제의 요구사항을 지키면서 스택에 문자를 넣으면 메모리 초과가 발생한다. 예를들어 9(9(9(9(9(9(9(9(99999(1)))))))))가 입력으로 들어온다고 하자. 문자열 '1'이 99만 x 9^8개 찍힌다. 계산해보니 약 42조 5천억이다. 문제의 메모리 제한이 128MB이므로, 당연히 메모리 초과가 나온다. 사실 처음에 스택에 문자 넣고 제출하다 알게됐다.

따라서 K(Q)에서 Q는 문자열 개수를 스택에 넣는 방식으로 해결해야한다. 우선 K에 대한 스택과, Q에대한 스택을 만들었다. 각각 따로 사용하는 이유는 Q에 대한 스택에서는 문자열의 개수를 K에 대한 스택에서는 정수K를 넣을 것이기 때문이다. 그리고 입력으로 들어온 문자열에 대해 현재 인덱스와 바로 다음 인덱스가 가리키는 문자를 살펴보고 다음을 적용했다.

• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 숫자를 가리키면, Q에 대한 스택의 마지막 값을 1 증가시킨다.
• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 )를 가리키면 Q에 대한 스택의 마지막 값을 1 증가시킨다.
• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 (를 가리키면, Q에 대한 스택에 0을 삽입하고, K에 대한 스택에 대해, 현재 인덱스가 가리키고 있는 숫자를 삽입한다.
• 현재 인덱스가 )를 가리키면, Q에 대한 스택에서 pop하여 얻은 값을 K에 대한 스택에서 pop하여 얻은 값과 곱한다. 그리고 Q에 대한 스택에서 원소를 갖고 있으면, pop하여 바로의 앞 결과와 더한후 Q에 대한 스택에 삽입한다.

(를 만날 때마다 Q에 대한 스택에 새로운 값, 0을 추가하여, 압축 해제에 적용될 대상을 구분했다. 그리고 )를 만날 때, K에 대한 스택의 마지막 값과 Q에 대한 스택의 마지막 값을 이용하여, 압축을 해제했다. 그리고 압축 해제에서 얻은 결과와 다음 압축 해제에 사용될 기존의 문자열의 길이를 더했다. 그래서 마지막 조건에 pop연산을 두 번했다. 다음 압축 해제에 적용될 기존의 문자열이 없다는 것은 1번째 pop연산 이후 Q에 대한 스택의 마지막 값이 0임을 의미한다.(e.g. 5(2(4)))

2. 코드

import sys

string = sys.stdin.readline().rstrip()
rep = []
chs = [0]
n = len(string)
i = 0

while i < n-1:
    if string[i].isdigit() and string[i+1].isdigit(): chs[-1] += 1
    elif string[i].isdigit() and string[i+1] == ')': chs[-1] += 1
    elif string[i].isdigit() and string[i+1] == '(':
        chs.append(0)
        rep.append(int(string[i])) 
    
    elif string[i] == ')':
        x = chs.pop() * rep.pop()
        if chs: x = chs.pop() + x
        chs.append(x)

    i += 1

if string[-1].isdigit(): chs[-1] += 1
else:
    x = chs.pop() * rep.pop()
    if chs: x = chs.pop() + x
    chs.append(x)

print(chs[0])