[백준/Python] #33848 퍼시스턴트 스택

문제

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

---

Algorithm

해당 스택의 3번 쿼리, 3 j: 최근 j개의 1번 또는 2번 쿼리를 취소한다. 취소할 수 있는 1번 또는 2번 쿼리가 j개 이상인 경우에만 주어진다. 를 수행하기 위해 이전 쿼리의 작동을 기억해야 할 필요가 있다.

그렇기에 메인 스택, 임시 스택을 두어 메인 스택에는 위의 쿼리를 진행한다. 임시 스택에는 1번 쿼리 수행시 0을 집어넣고, 2번 쿼리 수행시 메인 스택에서 제거된 수를 집어 넣는다.이후에 3번 쿼리가 들어오면 j번 만큼 임시 스택에서 pop연산을 진행하여 값이 0이면 메인 스택에서 제거, 값이 0이 아니면 해당 수를 메인 스택에 집어넣는 연산을 해주면 된다.

---

 

 

Code

import sys
input = sys.stdin.readline
INF = int(1e9)

main_stack = []
tmp_stack = []

for _ in range(int(input())):
    arr = list(map(int,input().split()))

    if arr[0] == 1:
        main_stack.append(arr[1])
        tmp_stack.append(0)
    elif arr[0] == 2:
        tmp_val = main_stack.pop()
        tmp_stack.append(tmp_val)
    elif arr[0] == 3:
        for i in range(arr[1]):
            tmp_val = tmp_stack.pop()
            if (tmp_val == 0):
                main_stack.pop()
            else:
                main_stack.append(tmp_val)
    elif arr[0] == 4:
        print(len(main_stack))
    elif arr[0] == 5:
        if(len(main_stack) == 0):
            print(-1)
        else:
            tmp_val = main_stack.pop()
            print(tmp_val)
            main_stack.append(tmp_val)