O(1)에 스택의 최솟값을 찾는 min stack 기법?

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

 

 

은행원이 현금 보유액 S를 가지고 있다.

 

고객이 입금을 하러 온다면, 입금 금액을 기록하고 고객이 가져온 현금을 새 봉투에 넣은 다음, 이전 입금 봉투 위에 쌓는다.

 

입금 봉투는 이처럼 스택 구조로 쌓이게 된다.

 

고객이 X원을 출금하러 온다면, 봉투 스택이 비어있는 경우 전액을 현금 보유액 S에서 지급

 

봉투에 든 금액들 중 가장 작은 금액보다 X가 작다면, 전액을 현금 보유액 S에서 지급

 

그렇지 않다면, 봉투 스택의 맨 위에서부터 하나씩 꺼낸 다음, 필요한 금액을 충당

 

마지막에 꺼낸 봉투에서 일부 금액만 사용하면, 남은 돈은 현금 보유액 S로 넣는다.

 

만약 모든 봉투를 다 사용했는데 X를 다 지급하지 못하면 남은 금액은 현금 보유액 S에서 지급

 

모든 입출금이 끝난 후, 현금 보유액 중 남은 금액과 봉투 스택에 남아 있는 모든 돈의 합을 구하라.

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

문제대로 구현하면 될듯

 

입금하러 온다면, x를 스택에 쌓아두고, 문제는 이 봉투 스택에서 최솟값을 알고 있어야, 

 

출금하러 온 사람의 금액 x와 봉투 스택의 최솟값을 비교할 수 있음

 

거래 횟수가 10^6이기 때문에 O(N)으로 매번 최솟값을 찾기는 어렵다

 

스택의 최솟값을 알기 위해 우선순위 큐도 준비해둠

 

import heapq
from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n,S = map(int,stdin.readline().split())

    stack = []
    queue = []

    visited = [0]*n

    for i in range(n):
        
        x = int(stdin.readline())

        if x > 0:
            
            stack.append((x,i))
            heapq.heappush(queue,(x,i))

 

 

출금하러 오는 경우는, 스택이 비어있는 경우 전액을 현금 보유액에서 지급하고

 

비어있지 않다면?

 

우선순위 큐를 이용해서 스택 내의 원소중 최솟값을 빠르게 찾아내

 

근데 문제는 이 값이 사용됐을 수도 있거든 

 

그래서 visited로 표시까지 해둬

 

이 최솟값보다도 x가 더 작다면 현금 보유액에서 다 지급하고

 

            
            x = -x

            if len(stack) == 0:
                
                S -= x
            
            else:
                
                while queue:

                    m,j = heapq.heappop(queue)

                    if visited[j] == 0:

                        break 
                
                heapq.heappush(queue,(m,j))
                
                if m > x:
                    
                    S -= x

 

 

아니라면 스택의 맨 위에서부터 금액을 하나씩 꺼내고,

 

x에 충당시켜

 

이 금액을 사용하면 우선순위 큐에서도 제거해야하는데, 이를 바로 제거하기는 어렵기 때문에 visited로 표시해둠..

 

스택을 다 썼는데도 x가 남아있으면? 현금 S에서 충당

 

이렇게 스택과 우선순위 큐, visited로 구현했음

 

                else:
                    
                    while stack:
                        
                        y,j2 = stack.pop()

                        if y > x:
                            
                            S += (y-x)
                            x = 0
                            visited[j2] = 1
                            break
                        
                        else:
                            
                            x -= y
                            visited[j2] = 1
                        
                        if x == 0:
                            
                            break
                    
                    if x > 0:
                        
                        S -= x
                    
    v = 0

    for i in range(len(stack)):
        
        v += stack[i][0]

    print(S,v)

 

 

근데 이렇게 하면 오래걸리더라고

 

근데 GPT피셜 O(1)에 우선순위 큐 없이도 스택의 최솟값을 알 수 있는 방법이 있다고함

 

 

 

방법은 스택에 값만 넣지 말고, (값, 현재 시점의 최솟값)을 넣는다고함

 

 

 

혹은 스택 두개를 사용해서, 하나의 스택에는 값을 넣고, 다른 스택에서는 현재 시점의 최솟값을 넣어서 관리할 수 있다

 

그러면 현재 시점의 최솟값은 다른 스택의 맨 위의 값을 보면 됨

 

주의할 점은 스택에서 값을 빼는 경우 최솟값을 저장하는 스택에서도 값을 동시에 빼줘야함

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n,S = map(int,stdin.readline().split())

    stack = []
    mins = []

    for _ in range(n):
        
        x = int(stdin.readline())

        if x > 0:
            
            stack.append(x)
            
            if len(mins) == 0:
                
                mins.append(x)
            
            else:
                
                if mins[-1] > x:

                    mins.append(x)

                else:

                    mins.append(mins[-1])

 

 

 

X를 입금할때, 스택에 X를 넣고, 현재 시점의 최솟값을 저장하는 mins 스택에는 mins가 크기가 0이라면 x가 최솟값이니 그대로 넣고

 

mins에 값이 존재하면, mins[-1]이 현재 시점의 최솟값이므로, mins[-1]과 x를 비교해서 x가 더 작으면 mins에 x를 넣는다.

 

이 x가 현재 시점의 최솟값이 되고, mins[-1]이 더 작으면 여전히 mins[-1]이 최솟값이므로 mins[-1]을 다시 append함

 

이러면 X를 출금할때는, 봉투 스택의 최솟값이 mins[-1]로 바로 알 수 있기 때문에 우선순위 큐를 사용한 부분이

 

m = mins[-1], if m > x: S -= x로 바로 구할 수 있다

 

그리고 봉투 스택에서 하나씩 금액을 빼서 충당할때 주의할 점은?

 

mins에서도 동시에 빼줘야한다는 점

 

 

        else:
            
            x = -x

            if len(stack) == 0:
                
                S -= x
            
            else:
                
                m = mins[-1]
                
                if m > x:
                    
                    S -= x

                else:
                    
                    while stack:
                        
                        y = stack.pop()
                        mins.pop()

                        if y > x:
                            
                            S += (y-x)
                            x = 0
                            break
                        
                        else:
                            
                            x -= y
                            
                        if x == 0:
                            
                            break
                    
                    if x > 0:
                        
                        S -= x
                    
    print(S,sum(stack))