[Python/BOJ] 1662. 압축

https://www.acmicpc.net/problem/1662

문제

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

입력

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

출력

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

풀이

Code

import sys
input = sys.stdin.readline

array = list(input().strip())
# 1. 스택 생성
stack = []
# 2.
length, multiple = 0, 0
for s in array :
    # 2-1. 입력받은 문자가 "("일 경우
    if s == "(" :
        # 2-1-1. 스택에 값 삽입
        stack.append((length - 1, multiple))
        length = 0
    # 2-2. 입력받은 문자가 ")"일 경우
    elif s == ")" :
        # 2-2-1. 스택에서 값 제거
        length_, multiple_ = stack.pop()
        # 2-2-2. 현재 길이 업데이트
        length = length * multiple_ + length_
    else :
        length += 1
        multiple = int(s)
# 3. 결과 출력
print(length)