[백준] 절댓값 힙

문제

 

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

---

풀이

from queue import PriorityQueue
import sys
input = sys.stdin.readline

n = int(input())
queue = PriorityQueue()

for i in range(n):
    request = int(input())
    if request == 0:
        if queue.empty():
            print('0')
        else:
            temp = queue.get()
            print(str((temp[1])))
    else:
        queue.put((abs(request), request))

 

---

설명

- 우선순위 큐 에 대해 인지하지 못했다.

 

우선순위 큐=pop을 할 때 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐
1. 원소의 추가가 O(lg N)
2. 우선순위가 가장 높은 원소의 확인이 O(1)
3. 우선순위가 가장 높은 원소의 제거가 O(lg N)