[🥇4 / 백준 1662 / 파이썬] 압축

 

 

 

 

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

 

 

풀이

 

문제에 나온 대로만 구현한다면 9(9(9(9(9(9(9(9(9(9(999)))))))))) 같은 입력에서 문자열의 길이가 9의 10승 이상 돌파하게 되므로 메모리 초과가 발생할 것이다.

 

따라서 문자열 압축을 풀어주되, 문자열을 전부 기록하는 것이 아니라 문자열의 총 길이만 기록하는 방식으로 풀어야 한다.

 

 

import sys
input = sys.stdin.readline

s = input().strip()
stack = []
for i in range(len(s)):
    # 여는 괄호일 경우 그냥 스택에 넣는다
    if s[i] == '(':
        stack.append(s[i])
    # 닫는 괄호일 경우 여는 괄호를 만날 때까지 순회하며 문자열의 길이를 센다.
    elif s[i] == ')':
        cnt = 0
        while True:
            cur = stack.pop()
            if cur == '(':
                break
            else:
                # cur은 1일 수도 있고, 압축을 해제한 문자열의 길이일 수도 있다.
                cnt += cur
        stack.append(stack.pop() * cnt)
    # 숫자이므로 문자열의 길이인 1을 스택에 넣는다. 단, 해당 숫자의 다음 문자열이 여는 괄호일 경우 곱셈을 하기 위해 그대로 넣어준다.
    else:
        stack.append(int(s[i]) if i+1 < len(s) and s[i+1] == '(' else 1)

print(sum(stack))