코딩테스트를 위한 기본 개념 3탄 - 우선순위큐(Priority)

 

 

백준을 풀다 보니 심심찮게 등장하는 우선순위큐. 이참에 간단하게 정리하고 넘어가야겠다.

 

1. 우선순위 큐(Priority)란?

1) 개념

기본적인 자료구조의 큐(Queue)에 우선순위를 도입한 자료구조가 우선순위 큐(Priority)이다. 즉, 각 값들은 우선순위를 가지고 있고 우선순위가 높은 값부터 처리되는 자료구조이다. 

 

2) 구현방법

우선순위 큐는 배열, 연결리스트, 힙(Heap)으로 구현가능하며 이 중 힙으로 구현하는 것이 가장 효율적이다.

• 배열, 연결리스트의 삽입/삭제 시간복잡도 : O(n)
•  힙의 삽입/삭제 시간복잡도 : O(log2n) - 완전 이진트리 구조이기 때문에!

3) Priority Queue vs. Heapq

Priority Queue는 Thread Safe하고 Heapq는 Non Safe하다. 

Thread Safe에 대해서는 잘 모르겠지만 코딩테스트를 할 때 염두할 내용은 아닌 듯 하여

코딩테스트에서 우선순위큐 문제를 만나면 속도가 더 빠르다고 알려진 Heapq를 사용하도록 해보자.

 

2. 파이썬 - Heapq 라이브러리 사용하기

2.1 heapq 메서드

- heapq.heappush(heap, item)

최소힙 자료구조 특성을 유지한 채로 item의 값을 heap에 추가하는 메서드. 가장 작은 값이 heap[0]에 위치하게 된다.

import heapq

num_lst = [3, 1, 2, 7, 5]
result = []
for num in num_lst :
    heapq.heappush(result, num)

 

 

- heapq.heappop(heap)

최소힙 자료구조 특성을 유지한 채로 heap의 첫 번째 요소를 삭제 후 반환하는 메서드

for _ in range(len(result)):
    print(heapq.heappop(result))

 

- heapq.heapify(list)

기존에 존재하는 리스트를 받아 Heap 구조로 변환하는 메서드

heapq.heapify(num_lst)

 

2.2 최대힙 구현하기

heapq는 기본적으로 최소힙 구조를 가지고 이를 응용해 최대힙을 구현해야 한다. 각 값들에 -(마이너스)를 취한 후 heap에 넣은 뒤 heappop으로 빼낸 값이 다시 -를 취해주면 최대값을 구할 . 수있다.

import heapq

num_lst = [1, 2, 3, 4, 5]
heap = []
max_heap = []

for num in num_lst:
    heapq.heappush(heap, -num)
print(heap)

for i in range(len(heap)):
    max_heap.append(-heapq.heappop(heap))
print(max_heap)

 

 

3. 실전 문제 풀기 - 파이썬

3.1 백준 - 2075번: N번째 큰 수

import heapq

heap=[]
n = int(input())

for _ in range(n) :
    n_lst = map(int, input().split())
    for i in n_lst :
        if len(heap) < n :
            heapq.heappush(heap, i)
            
        else :
            if heap[0] < i :
                heapq.heappop(heap)
                heapq.heappush(heap, i)
                
print(heap[0])

 

3.2 백준 - 1655: 가운데를 말해요