문제
세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.
상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.
세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.
방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.
입력
첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다.
이후 N개의 줄에 걸쳐 1번부터 N번 손님의 주문 시각 ti(1 ≤ ti ≤ 86,400), 선택한 포장지의 색깔 ci(ci = "B"|"R"), 주문한 선물의 개수 mi(1 ≤ mi ≤ 100)가 주어진다.
ti는 가게가 오픈한 지 ti초 후에 손님이 주문했음을 뜻하며 ci는 포장지의 색깔을 의미하는 알파벳으로 "B"는 파란색을, "R"은 빨간색을 의미한다. 주어지는 입력은 시간의 흐름에 맞게 ti의 오름차순으로 주어지며, 서로 같은 시간에 주문한 손님은 없다.
코드
import heapq
blue, red, n = map(int, input().split())
queue = list()
heapq.heapify(queue)
r_end = b_end = 0
for i in range(n):
time, color, cnt = map(str, input().split())
time = int(time)
cnt = int(cnt)
j = 0
if color == 'R' and r_end > time:
time = r_end
elif color == 'B' and b_end > time:
time = b_end
while j < cnt:
if color == 'B':
heapq.heappush(queue, (time + blue * j, 'B'))
else:
heapq.heappush(queue, (time+ red * j, 'R'))
j+=1
if color == 'B':
b_end = time + blue * j
else:
r_end = time + red * j
b = list()
r = list()
for j in range(len(queue)):
poped = heapq.heappop(queue)
# print(poped)
if poped[1] == 'B':
b.append(j+1)
else:
r.append(j+1)
print(len(b))
for a in b:
print(str(a)+" ", end="")
print()
print(len(r))
for d in r:
print(str(d)+" ", end="")설명
우선순위 큐를 사용해 문제를 풀었다. n명의 손님의 주문을 받을 때 마다 상자의 색깔을 구분해서 각 물건의 포장 시작시간을 저장하고 다 끝나면 heaq.pop을 해주면서 순서에 맞춰서 몇번째 선물을 누가 포장했는지 출력만 해주는데 여기까지만 구현한다면 100점만 받을 것이다. 140점 만점을 받기 위해서는 다수의 손님이 같은 색상으로 포장을 하는데 손님이 주문한 시간에 앞에 손님의 포장이 끝나지 않았을 경우를 생각해서 손님이 주문한 시간에 앞의 손님의 포장이 끝나지 않았다면 그 시간만큼 딜레이를 시켜줘야 한다. 이것까지 구현한다면 140점 만점을 받을 것이다.
