[python] 우선순위 큐_백준 문제풀이

우선순위 큐

우선순위 큐는 데이터를 추가한 순서와 상관없이, 데이터를 꺼내는 순서를 오름차순으로 하는 특징이 있다.
즉, 내부의 데이터를 항상 정렬된 상태로 보관하는 로직이 있으며, heapq 모듈을 통해 구현 가능하다.
put(), get() 메서드 모두 O(log n)의 시간복잡도를 가진다.

1️⃣ 클래스 임포트 및 선언
PriorityQueue 클래스는 queue 내장 모듈에서 제공한다.

from queue import PriorityQueue
queue = PriorityQueue()

만약 사이즈 제한을 두고 싶다면 선언 시, 속성으로 maxsize=?을 넣어준다.

2️⃣ 원소 추가와 제거(반환)
queue.put(x)로 추가, queue.get()으로 제거(반환)할 수 있다.
오름차순의 순서로 반환된다.

만약 역순으로 반환하고 싶다면 (-x, x)의 튜플 형식으로 삽입하면 된다.

3️⃣ 기타 메서드

• queue.qsize(): 큐의 크기를 반환한다. len() 사용 불가!
• queue.empty(): 큐가 비었는지 여부를 True/False 값으로 리턴한다.
• queue.full(): 큐의 사이즈가 가득 찼는지 여부를 True/False 값으로 리턴한다.

그렇다면 백준 문제를 풀어보자!

11279번 - 최대 힙

from Queue import PriorityQueue
import sys

input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()

for n in range(N):
    command = int(input())
    if command == 0:
        if queue.empty():
            print(0)
        else:
            x = queue.get()
            print(x[1])
    else:
        queue.put((-command, command)) 

1927번 - 최소 힙

from Queue import PriorityQueue
import sys

input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()
for n in range(N):
    comm = int(input())
    if comm == 0:
        if queue.empty():
            print(0)
        else:
            print(queue.get())
    else:
        queue.put(comm)

11286번 - 절댓값 힙

from Queue import PriorityQueue
import sys

input = sys.stdin.readline
N = int(input())
queue = PriorityQueue()

for n in range(N):
    comm = int(input())
    if comm == 0:
        if queue.empty():
            print(0)
        else:
            x = queue.get()
            print(x[1])
    else:
        if comm < 0:
            queue.put((-comm, comm))
        else:
            queue.put((comm, comm))