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

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

1662번: 압축

 

 

번역을 해서 가져온 외국 문제는 설명이 늘 부족하다.

 

예제1의 33(562(71(9)))는 K(Q)의 형태로 되어있는데 전개를 하면

33(562(79))가 되고

33(567979)가 되고 마지막으로

3567979567979567979가 된다. 그래서 총 길이는 19가 된다.

 

import sys
string = sys.stdin.readline().rstrip()
stack, cnt = [], 0 #1
before = '' #2
for char in string:
    if char == '(': #3
        stack.append((before, cnt-1))
        cnt = 0
    elif char == ')': #4
        k, lastLen = stack.pop()
        cnt = lastLen + k*cnt
    else: #5
        cnt += 1
        before = int(char)
print(cnt)

 

#1 : 스택과 압축해제한 문자의 길이를 저장할 변수 생성

#2 : ( 직전 곱할 숫자를 저장할 변수

#3 : 여는 괄호일때 ( 직전의 숫자와 ( 이전까지의 숫자들의 길이 저장 cnt-1인 이유는 곱하는 숫자k는 이전문자에 포함되지 않기 때문에 남은 문자는 곱을 해준 문자 앞에 붙기 때문이다.

562(79)라 할떄 56(7979)가 되는데 숫자 2는 곱을 해주고 이전문자 56은 그대로 앞에 붙는다.

그래서 lastLen + k * cnt가 되는것이다.

#4 : 닫는 괄호일때 곱할 숫자 k와 이전 문자열의 길이 lastLen을 stack에서 뽑아주고 계산을 수행한다.

#5 : 숫자인 경우 길이를 나타내는 변수 cnt +1 그리고 숫자 before에 저장

 

이 분의 블로그를 참고했다. 

https://westmino.tistory.com/78