9280. 진용이네 주차타워
문제
문제를 요약하면
1. 차가 주차장에 도착하면, 비어있는 주차 공간이 있는지 검사
2. 비어있는 공간이 없다면, 빈 공간이 생길 때까지 차량을 입구에서 기다리게 함
3. 비어있는 공간이 있다면 곧바로 주차를 시킴
이때, 주차 공간 선택 기준은 주차 가능한 공간 중 번호가 가장 작은 곳 입니다. 여기에 대기하는 운전자들은 새치기를 하지 않는 조건이 붙습니다.
주차 요금은 차량의 무게와 주차 공간마다 따로 책정된 단위 무게당 금액을 곱한 가격입니다. 즉, 이용시간은 고려하지 않습니다.
예를들어, 1번 주차장의 무게당 가격이 100원이고 차량의 무게가 5라면 주차가격은 500원이 됩니다.
풀이(스택, 큐, 우선순위 큐)
스택은 주차한 차량, 위치를 저장하고, 큐에는 대기하고 있는 차량을 저장하고, 우선순위 큐에는 주차 가능한 공간이 저장됩니다.
우선순위 큐이기 때문에 항상 번호가 작은 값이 pop이 되는 점을 이용하였습니다.
-
input()한 데이터를 변수에 저장합니다.
cost는 주차 공간의 단위 무게, weight는 차량 무게, graph는 출입에 관한 정보를 저장합니다. -
우선순위 큐를 초기화합니다.
아직 처음이기 때문에 주차 가능한 공간은 0~ n-1까지 될 것 입니다. -
들어일 때
stack은 주차된 차량을 저장하는데 만약 stack의 길이가 주차 공간 n보다 작으면 주차할 수 있습니다. 반면에 주차장이 꽉 차있으면 큐에 대기시켜야 합니다.
그리고 heap에서 pop을 하게 되면 가장 작은 번호의 주차 공간을 가져오고 stack에 num, pos를 저장합니다. -
나갈 때
stack에서 해당 num의 절대값이 있다면 stack에서 제거합니다. 그러면 해당 주차 공간 stack[i][1]은 비어 있게 되므로 heapq에 push합니다. 그리고 queue에 대기된 차량이 있다면 주차 공간을 가져오고 stack에 넣습니다.
T = int(input())
from collections import deque
from heapq import heappush, heappop
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n, m = map(int, input().split(" "))
cost = [int(input()) for _ in range(n)]
weight = [int(input()) for _ in range(m)]
graph = [int(input()) for _ in range(2*m)]
stack, queue, ans, heap = [], deque(), 0, []
## heapq 초기화
for i in range(n):
heappush(heap, i)
for num in graph:
if num > 0: ##들어옴
if len(stack) < n: ##주차되어 있는 공간이 n보다 작거나 같을 때 주차가능
pos = heappop(heap)
stack.append([num, pos])
continue
else: ## 주차장 꽉 차있으면 대기시켜야 함 큐에
queue.append(num)
else: ##나감
## stack에서 해당 num pop해주기
for i in range(len(stack)):
if stack[i][0] == abs(num):
heappush(heap, stack[i][1])
ans += weight[stack[i][0] - 1] * cost[stack[i][1]]
stack.pop(i)
if queue:
pos = heappop(heap)
stack.append([queue.popleft(), pos])
break
print("#" + str(test_case) + " " + str(ans))