[BOJ/백준] 1662 압축 파이썬

문제 링크 : https://www.acmicpc.net/problem/1662

1662번: 압축

 

문제 설명이 너무 없었다.

예제를 보고 설명하면 아래와 같다.

 

입력 예제 1: 33(562(71(9)))

압축은 K(Q)형태로 되어 있다.

K는 한자리 이므로 K와 Q를 구분하면 아래와 같을 것이다.

3 3(56 2(7 1(9)))

 

가장 안쪽 7 1(9)을 보자

K는1 Q는 9이므로 9가 될 것이고 앞의 7과 합쳐져 79가 된다.

그다음으로 가면

56 2(79)가 되고 79를 2번 반복하고 합친다면 567979가 된다.

그다음으로 가면

3 3(567979)가 된다 567979가 3번 반복하고 합치면 3567979567979567979이 된다.

따라서 답은 길이인 19가 된다.

 

예제는 K(K(Q(K(Q)))이런식이지만

K(K(Q)K(Q))이런식으로도 압축이된다. 이점을 고려야한다.

 

나는 스택으로 풀이했다.

처음에 그냥 문자다 만들어서 했더니 메모리초과가 났다.

당연하다

9(9(9(9(9(9(9(9(9)...))))) 이런식으로 나온다면 9^50이 되니 굉장히 크므로 초과과 날것이다.

 

그래서 그냥 길이랑 K값만 구해서 스택에 넣어줬다.

 

모든 문자를 일단 검사하자.

숫자라면 길이를 1더해주고, before에 그 값을 넣어주자.

before는 K를 구하기 위함이다. '(' 바로 전 숫자가 K가 되기 때문에 이전 숫자를 계속 저장했다.

 

만약 '(' 라면 [길이-1,before]를 스택에 넣어줬다.

길이-1인 이유는 K는 문자에 치지 않기 때문이다.

그리고 문자 길이를 0으로 초기화 해주자.

 

그리고 만약 ')'라면 스택에서 정보 하나 빼온 다음 길이를 수정한다.

스택에는 이전 문자의 길이, K값이 들어있다.

그래서 현재 문자의 길이*k+이전 문자의 길이로 바꾸자.

 

개똥같은 설명 주의....

 

1(12(3)2(4)) 을 해보자.

3을 체크하는 시점에 큐의 상태는 아래와 같을 것이다.

[[0,1],[1,2]]이고 [1,2]가 스택 포인터이다.

 

그래서 3을 보는 시점에서 현재 문자의 길이는 1이고 ')' 가 왔기 때문에 현재 문자 길이를 수정한다.

1*2+1이 안쪽 1 2(3)을 수행했을 때 길이가 된다.(133)

 

다음 숫자가 왔다

그러므로 cnt와 before를 수정하자

그다음 '('가 왔으므로 정보를 스택에 넣자

 

다음 '4'가 나왔다. 현재 문자의 길이는 1이고 스택의 탑에는 [2,2]이다.

그러므로 문자의 길이는 1*3+2 = 4 가 된다.(13344)

 

다음 ')'가 나왔고 스택의 탑은 [0,1]이다

따라서 답은 5*1+0 = 5가 된다.

 

 

from sys import stdin

input = stdin.readline

input_data = input().strip()

def solv():
    stack = []

    cnt=0
    before=''
    for c in input_data:
        if c == '(':
            stack.append([cnt-1,before])
            cnt = 0
        elif c == ')':
            info = stack.pop()
            cnt = cnt*info[1]+info[0]
        else:
            cnt += 1
            before = int(c)
    print(cnt)
solv()