[Algorithm] 백준 BOJ 1662 압축(python 파이썬)

BOJ 1662 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다.

K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 

이 Q라는 문자열이 K번 반복된다는 뜻이다.

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 압축된 문자열 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

풀이

# boj 1662 압축

s = str(input())
tmp = ''
stack = []
l = 0
for i in s :
    if ord(i) >= 48 and ord(i) <= 57: 
        tmp, l = i, l+1
    elif i == '(' : 
        stack.append([tmp, l-1])
        l = 0
    elif i == ')' : 
        n, p = stack.pop() 
        l = int(n)*l+p 
print(l)