우선 순위 큐 - BOJ : 1202 보석 도둑

우선 순위 큐

queue 는 먼저 input 된 것이 가장 먼저 output 되는 자료구조였다. 우선순위 큐는 단순히 먼저 들어간 것이 일찍 나오는 것이 아니라 우선순위에 따라 먼저 나오는 것이 결정된다.

구현

우선순위 큐를 구현하는 방법에는 3가지가 있다.

1. 배열 이용하기

데이터 삽입 및 삭제 과정에서 데이터를 한칸 씩 당기거나 미는 연산을 반복해야하고,
삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야한다는 단점이 있다.

2. 연결 리스트 이용하기

연결리스트?

데이터와 다음 노드의 주소를 담고 있는 node들이 한 줄로 연결되어 있는 방식

이미지 출처

연결 리스트를 이용하여 우선 순위 큐를 구현하면 첫번째 노드부터 마지막 노드까지 우선순위를 모두 비교해야 하는 경우가 생기기도 한다.

3. 힙(HEAP) 이용하기

from queue import PriorityQueue

생성하기

que = PriorityQueue()
que2 = PriorityQueue(maxsize=8) # 특정 최대 크기 부여

원소 추가하기

que.put(4)
que.put(1)

원소 삭제하기 / 가져오기

print(que.get())
print(que.get())

정렬 기준 변경하기

(우선순위, 값) 의 tuple 형태로 데이터를 추가하고 제거한다.
que.put((1, "a"))
que.put((2, "b"))

put(), get()의 시간복잡도는 O(log n)

heapq 이용하기

import heapq

생성하기

heap = []
# 이미 원소가 들어있는 리스트이면,
v = [4,1,2]
heapq.heapify(v)

원소 추가하기

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
# (우선순위, 원소) 의 형식으로 추가도 가능하다. 
heap2 = []
heapq.heappush(heap2, (1, 4))

원소 삭제하기

print(heapq.heappop(heap)) # 가장 작은 원소를 삭제 후에 그 값을 return 한다. 

삭제하지 않고 얻기

print(heap[0])

1202 문제풀이

보석과 가방을 가벼운 것부터 정렬해준다.
우선순위 큐를 이용하여 q에 가방 무게보다 가벼운 보석들을 모두 넣어주고 그 중 가장 비싼 것들을 꺼내는 작업을 반복한다.

import sys
from queue import PriorityQueue

num_gem, num_bag = list(map(int, list(sys.stdin.readline().strip().split())))
gems = [list(map(int, list(sys.stdin.readline().strip().split()))) for _ in range(num_gem)]
bags = [int(sys.stdin.readline().strip()) for _ in range(num_bag)]

# gems 와 가방은 가벼운것부터 정렬
gems.sort(key=lambda x: (x[0]))
bags.sort()

q = PriorityQueue()
idx = 0
sum = 0
for i in range(num_bag):
    while idx < num_gem and bags[i] >= gems[idx][0]:
        q.put((-gems[idx][1], gems[idx][1]))
        idx += 1
    if not q.empty():
        sum += q.get()[1]



print(sum)