Tag: priority queue

import heapq

N = int(input())

lessons = []
for _ in range(N):
    i, s, e = map(int, input().split())
    lessons.append((s, e, i - 1))

lessons.sort()
room_end = [(lessons[0][1], 1)]
result = [0] * N
result[lessons[0][-1]] = 1
room_cnt = 1

for s, e, i in lessons[1:]:
    # 가장 일찍 끝나는 방
    min_end, room_i = heapq.heappop(room_end)
    # 그 방을 사용 가능할 경우
    if min_end <= s:
        heapq.heappush(room_end, (e, room_i))
        result[i] = room_i
    # 사용 못하는 경우 -> 새로운 방
    else:
        # 원래대로 복구
        heapq.heappush(room_end, (min_end, room_i))
        # 새로운 방 만들기
        room_cnt += 1
        result[i] = room_cnt
        heapq.heappush(room_end, (e, room_cnt))

print(room_cnt)
print(*result, sep='\n')

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    num = int(input())
    pq.put(num)

result = 0

while pq.qsize() > 1:
    tmp = pq.get()
    num = pq.get()
    result += tmp + num
    pq.put(tmp + num)

print(result)

우선순위 큐에 입력으로 들어온 카드 뭉치의 크기를 삽입하고 반복문을 시작한다.

우선순위 큐의 첫 번째, 두 번째 원소를 빼내서 더해준다 (카드 뭉치를 합침). 그리고 이를 결과가 저장될 result 함수에 저장해준다 (합칠 때 비교한 횟수를 반영). 마지막으로 첫 번째와 두 번째 원소의 합을 다시 우선순위 큐에 넣어준다. 다시 넣어주면 합쳐진 카드 뭉치를 자연스럽게 다시 합칠 수 있다.