[Python] 백준 11279번: 우선순위 큐 구현

 

📎 백준 11279번 풀러 가기!

 

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

---

오늘은 우선순위 큐 문제를 풀어보았다!

우선순위 큐의 개념 자체는 알고 있었는데,

어떤 식으로 구현되어있는지, 그리고 어떻게 활용하는지는 이번에 처음 공부해보았다.

 

파이썬에는 PriorityQueue와 heapq를 제공하는데,

PriorityQueue는 heapq를 기반으로 구현된 자료구조인데,

lock을 제공하기 때문에 thread-safe한 반면

heapq는 lock을 제공하지 않기 때문에 no thread-safe하다고 한다.

 

lock을 제공하지 않는다는 것은 lock을 하는데 드는 비용이 적다는 것을 의미한다.

따라서 코딩테스트를 볼 때는 PriorityQueue보다는 heapq를 주로 사용한다고 한다.

 

만약 multi-threading을 사용해야한다면 PriorityQueue를 사용하는 것이 맞겠지만

코딩테스트에서 multi-threading을 사용하는 일도 적기도 하고

시간 내에 풀어야 하는 문제도 많기 때문!

 

지난 학기에 C로 safety한 multi-threading을 구현하면서

mutex lock이나 semaphore 등을 사용하면서 시간 측정도 참 많이 했었는데,

확실히 lock을 사용하지 않고도 구현할 수 있는 것들은 lock을 사용하지 않는게 훨씬 낫다 매우매우

 

앞으로 이 차이점을 머리에 새기고,

우선순위큐를 사용해야하는 경우 상황에 맞는 자료구조를 선택해야지😊

---

아래는 내가 구현한 코드👇

import heapq
import sys

q = []

N = int(sys.stdin.readline())

while N > 0:
    N -= 1

    x = int(sys.stdin.readline())
    if x == 0:
        if q:
            temp = heapq.heappop(q)[1]
            print(temp)
        else:
            print(0)
    else:
        heapq.heappush(q, (-x, x))

---

✍ 새로 안 사실들

1. 파이썬에서 우선순위 큐는 PriorityQueue와 heapq를 통해 구현할 수 있다.

2. PriorityQueue는 heapq를 기반으로 구현된 자료구조이다.

3. PriorityQueue는 lock을 제공하기 때문에 thread-safe하지만, heapq는 lock을 제공하지 않아 no-thread-safe 하다.