Point 💡

처음을 설계할 때, 우선순위를 1. 데드라인, 2. 컵라면 수로 잡고, 큰 순서대로 정렬을 한 뒤에 카운트와 비교를 하는 방법을 취했는데, 다음과 같은 예외를 발견할 수 있었다.

4
1 50
2 30
3 60
3 70

# 답 : 180
# 출력 : 160  

그렇다면, 어떻게 처리해야할까?

배열을 오름차순 정렬한 뒤, 큐에 일단 컵라면 수를 다 집어넣고, 큐의 길이보다 데드라인 숫자가 더 작으면, 큐에서 pop을 시킨다. 이때, 최소힙이므로 pop을 시키면 가장 작은 숫자가 나오므로 컵라면 수의 최댓값을 구할 수 있다.

(1, 50) , len(queue) = 0 -> queue[50]
(2, 30) , len(queue) = 1 -> queue[50, 30]
(3, 60) , len(queue) = 2 -> queue[60, 50, 30]
(3, 70) , len(queue) = 3 -> queue[70, 60, 50, 30], queue.pop() : queue[70, 60, 50]

Priority Queue

: pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

배열, 연결리스트, 힙 3가지로 구현할 수 있지만, 배열이나 연결리스트로 구현할 경우, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 당기거나 미는 연산을 계속 해야한다.

또한, 삽입의 위치를 찾기위해 배열에 저장된 모든 데이터와 우선순위를 비교해야한다. 연결리스트의 경우, 삽입의 위치를 찾기 위해 첫번째 노드부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행해야할 수도 있다 → 성능저하

따라서, 우선순위 큐를 구현할 때는 일반적으로 힙으로 구성한다.

import heapq

# 최소힙 구현 (default)
heap = []

# [1, 2, 3, 4, 5]
for i in range(1, 6):
		heapq.heappush(heap, i)

# 작은 숫자 순서대로 1, 2, 3, 4, 5 출력
for i in range(5):
		print(heapq.heappop(heap))

####

# 최대힙 구현
heap = []
values= [1, 5, 3, 2, 4]

# [-5, -4, -3, -2, -1]
for value in values:
		heapq.heappush(heap, -value)

# 큰 숫자 순서대로 5, 4, 3, 2, 1 출력
for i in range(5):
		print(-heapq.heappop(heap))

import java.util.PriorityQueue;
import java.util.Collections;

// 우선순위가 낮은 숫자인 int형 우선순위큐 (최소힙)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

// 우선순위가 높은 숫자인 int형 우선순위큐 (최대힙)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());

priorityQueue1.add(1);
priorityQueue1.offer(20);

// 첫번째 값을 반환하고, 제거 + 비어있다면 null 반환
priorityQueue1.poll();

// 첫번째 값 제거 + 비어있다면 예외 발생
priorityQueue1.remove();

// 첫번째 값을 반환만 하고, 제거 X + 비어있다면 null 반환
priorityQueue1.peek();

// 첫번째 값을 반환만 하고, 제거 X + 비어있다면 예외 발생
priorityQueue1.element();

// 초기화
priorityQueue1.clear();