백준 온라인 저지, 자료구조 / 1662번: 압축 (파이썬 / 백준 골드문제)

문제

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

입력

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

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

제한

예제 입력 1

33(562(71(9)))

예제 출력 1

19

예제 입력 2

123

예제 출력 2

3

예제 입력 3

10342(76)

예제 출력 3

8

예제 입력 4

0(0)

예제 출력 4

0

예제 입력 5

1(1(1(1(1(1(1(0(1234567890))))))))

예제 출력 5

0

예제 입력 6

1()66(5)

예제 출력 6

7

힌트

접근 방법

- 문자열을 하나씩 탐색하며 (가 등장하면 그 앞의 숫자를 다른 스택에 저장한다.
- 이후 숫자를 하나씩 세어 가며 )가 등장할 경우 해당 숫자를 스택의 마지막에 저장되어있는 숫자만큼 곱한 뒤, 이를 이전에 세었던 숫자에 더해준다.
- 위의 과정을 반복하며 최종 문자열의 길이를 출력한다.

코드

# https://www.acmicpc.net/problem/1662
# 접근 방법
# 문자열을 하나씩 탐색하며 (가 등장하면 그 앞의 숫자를 다른 스택에 저장한다.
# 이후 숫자를 하나씩 세어 가며 )가 등장할 경우 해당 숫자를 스택의 마지막에 저장되어있는 숫자만큼 곱한 뒤, 이를 이전에 세었던 숫자에 더해준다.
# 위의 과정을 반복하며 최종 문자열의 길이를 출력한다.

s = input()
stack = []
stack.append([0, 1])
for i in range(len(s)):
    if s[i] != '(' and s[i] != ')':
        stack[-1][0] += 1
    else:
        if s[i] == '(':
            stack[-1][0] -= 1
            stack.append([0, int(s[i-1])])

        if s[i] == ')':
            count, mul = stack.pop()
            stack[-1][0] += count * mul
            
print(stack[0][0])