[ BOJ ] 23350 : K 물류창고 ( SILVER 2 ) / Python

문제

K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 컨테이너의 무게만큼 비용을 발생시킨다.

컨테이너마다 우선순위가 있는데 우선순위는 1 이상 M 이하의 정수로 표현된다. 우선순위가 1에 가까울 수록 높은 우선순위를 가지고, M에 가까울 수록 낮은 우선순위를 가진다. M개의 각 우선순위에 대하여 해당 우선순위를 갖는 컨테이너가 적어도 하나 존재한다.

컨테이너는 레일을 통해 하나씩 오고, 우선순위가 낮은 컨테이너를 먼저 적재한다. 낮은 우선순위의 컨테이너들이 모두 적재되지 않은 상태에서 높은 우선순위의 컨테이너가 온다면 레일의 처음으로 보낸다. 레일의 처음으로 보낼 때, 컨테이너의 무게만큼 비용이 발생한다. 낮은 우선순위의 컨테이너가 온다면, 무조건 적재한다.

컨테이너의 우선순위가 같을 땐, 무게가 무거운 컨테이너를 아래에 위치시킨다.

컨테이너의 우선순위가 같으면서 무게도 같은 경우는 어느 것이 위에 있어도 상관없다.

우선순위는 같으나, 무게가 가벼운 컨테이너가 먼저 적재돼 있을 경우, 가벼운 컨테이너가 무거운 컨테이너 위로 갈 수 있도록 컨테이너를 빼내고 다시 적재한다. 이 과정을, 가벼운 컨테이너가 모두 빠질 때까지 반복한다. 이 과정에서 컨테이너를 뺄 때와 적재될 때 컨테이너의 무게만큼 비용이 발생한다.

작업이 모두 끝난 후 도커 씨가 부담해야 할 비용을 출력하자.

입력

첫째 줄엔 컨테이너의 개수 N과 우선순위의 종류 M이 주어진다. (1 ≤ M ≤ N ≤ 100)

2번째 줄부터 N + 1번째 줄까지는 컨테이너들의 우선순위 P(1 ≤ P ≤ M), 무게 W (1 ≤ W ≤ 100)가 순서대로 주어진다.

레일에 배치되는 순서는 입력으로 주어지는 컨테이너의 순서와 동일하다.

모든 입력은 1 이상의 정수이다.

출력

로봇이 들어올린 무게들의 합을 출력한다.

풀이 과정

1. 컨테이너들의 우선순위 개수를 세서, 가장 낮은 우선순위 컨테이너를 전부 적재했는지 여부를 확인한다.

2. 레일에 배치되는 순서대로 컨테이너를 적재하려고 시도하며, 만약 적재하려고 하는 컨테이너가 낮은 우선순위라면 적재한다. 그렇지 않으면 레일의 가장 뒷 순서로 보낸다. ( 해당 컨테이너의 무게를 비용으로 추가한다. )

3. 이미 적재된 공간에 적재하려는 컨테이너보다 가벼운 컨테이너가 있다면, 다른 공간에 이미 적재된 컨테이너를 빼면서 무게 순으로 적재될 수 있도록 한다. 적재하려는 컨테이너를 올바른 위치에 적재한 뒤 다른 곳에 빼놓은 컨테이너를 원상복구한다. ( 이때 건드린 컨테이너들의 무게를 비용으로 추가한다. )

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]

queue = deque()
priority_dict = {}

for a in arr:
    if priority_dict.get(a[0], -1) == -1: priority_dict[a[0]] = 1 
    else: priority_dict[a[0]] += 1 
    queue.append(a)

priority_list = list(priority_dict.items())
for p in range(len(priority_list)): priority_list[p] = list(priority_list[p])
priority_list.sort(key=lambda x:-x[0])

result_stack = []
last_stack = []
cost = 0

while queue:
    now = queue.popleft()
    if priority_list[0][0] == now[0]:
        # 적재
        while len(result_stack) > 0 and result_stack[-1][0] == now[0] and result_stack[-1][1] < now[1]:
            go = result_stack.pop()
            cost += go[1]
            last_stack.append(go) 
        result_stack.append(now)
        cost += now[1]
        while last_stack:
            go = last_stack.pop()
            cost += go[1]
            result_stack.append(go)
        
        priority_list[0][1] -= 1
        if priority_list[0][1] == 0:
            del priority_list[0]
    else:
        # 적재 안함
        queue.append(now)
        cost += now[1]

print(cost)