백준 23350 - K 물류창고 (파이썬)

난이도

실버 2

 

유형

자료구조 - 스택

 

해결

특별할 것 없이 그냥 구현해주면 해결되는 문제이다.

 

코드

from sys import stdin
from heapq import heappush,heappop
from collections import deque,defaultdict
input=stdin.readline

n,m=map(int,input().split())
ml={i:defaultdict(int) for i in range(1,m+1)}
arr=deque([])
sarr=deque([])
for i in range(n):
    p,w=map(int,input().split())
    ml[p][w]+=1
    arr.append((p,w))
sarr=sorted(arr)
now=m
ans=0
s=deque([0])
while arr:
    prior,front=arr.popleft()
    while now!=prior:
        ans+=front
        arr.append((prior,front))
        prior,front=arr.popleft()
    ml[now][front]-=1

    if ml[now][front]==0:
        del ml[now][front]
    if s:
        lift=deque([])
        while s and s[0]<front:
            top=s.popleft()
            lift.append(top)
            ans+=top
        s.appendleft(front)
        while lift:
            top=lift.pop()
            ans+=top
            s.appendleft(top)
        ans+=front
    if len(ml[now])==0:
        s=deque([0])
        now-=1

print(ans)