[백준][Python] 11286 절댓값 힙 - 우선순위 큐(Priority Queue)

문제

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

11286번: 절댓값 힙

---

설계

주어진 입력의 개수는 최대 100,000개이고, 주어진 시간은 1초이다.

따라서 이 문제는 최소 $ O(n \mathrm{log}n) $의 시간복잡도로 해결해야 한다.

 

입력을 하는 과정에서 n번의 연산을 하는 것은 어쩔 수 없으니,

저번과 같이 답을 구하는 과정에서 $O(1)$의 시간이 걸리는 큐나 덱을 사용해보자.

 

여기서 포인트는 데이터를 절댓값 순으로 정렬해야한다는 것이다.

이렇게 데이터에 우선순위가 필요한 경우, 우선순위 큐(Priority Queue)를 이용하면 된다.

---

우선순위 큐(Priority Queue)

우선순위 큐의 초기화

from queue import PriorityQueue

pqueue = PriorityQueue()

---

우선순위 큐의 기본 메서드

pqueue.put(data)	# 데이터 추가
pqueue.get()		# 큐에서 데이터 삭제
pqueue.qsize()		# 큐 사이즈 리턴
pqueue.empty()		# 큐가 비어있는지 확인

 

여기서 주목해야 하는 함수는 put(data) 함수이다.

파이썬에서는 데이터의 순서가 정렬의 우선순위가 된다.

따라서, 절댓값을 기준으로 데이터를 정렬하는 경우 put((abs(data), data))의 튜플 형태로 데이터를 저장해

절댓값을 기준으로 정렬하고 데이터는 1번째 인덱스에 접근해 꺼내서 사용할 수 있게 된다.

 

다른 기준을 토대로 정렬을 해야한다면 튜플의 0번째 인덱스에 알맞은 정렬 기준을 넣어 사용하면 된다.

---

코드

from queue import PriorityQueue
import sys

input = sys.stdin.readline

pqueue = PriorityQueue()

N = int(input())

for _ in range(N):
    x = int(input())
    if x == 0: 
        if pqueue.empty():
            print("0")
        else:
            print(str(pqueue.get()[1]))
    else:
        pqueue.put((abs(x), x))