[Baekjoon, Python] 11286번 : 절댓값 힙

도입

백준 단계별 풀기에서 우선순위큐 세 번째 문제이다.

백준 11286번 문제, 입력, 출력

---

백준 11286번 입출력 예제 1

---

풀이

0. 우선순위큐는 큐의 FIFO의 구조가 아닌, 들어간 순서에 상관없이 우선순위가 높은 순서대로 OUT한다. 여기서, 최소힙이란, 루트노드에 가장 작은 값이 위치하는 것이다. 부모 노드는 항상 자식 노드에 들어있는 값 보다 작다.

 

1. 우선순위큐에 대한 자료구조에 대한 지식이 필요하다. 만약 우선순위큐 자료구조에 대한 지식이 아직 없다면, 먼저 해당 지식을 먼저 알아보자. 필자는 파이썬에서 제공하는 heapq를 활용하여 문제를 풀 예정이다. 자바의 PriorityQueue 클래스와 결을 같이 한다. heapq는 말그대로 힙의 자료구조를 활용하여 우선순위큐를 구현하는 것인데, 힙을 사용하는 이유, 즉 배열과 연결리스트를 사용하지 않는 이유는 시간복잡도에서 우선순위큐를 구현하는데 효율의 차이가 있기 때문이다. 자세한 사항은 자료구조 우선순위큐를 찾아보도록 하자.

 

2.1. heapq 라이브러리 내 함수

  - heappush(heap, item)

  - heappop(heap)

  - heapreplace(heap, item)

  - heappushpop(heap, item)

  - heapify(x)

2.2. heapq 라이브러리 내 함수 (Maxheap 버전)

  - _heappop_max(heap)

  - _heapreplace_max(heap, item)

  - _heapify_max(x)

 

3. heappush를 할 때, 튜플로 힙에 넣을 수 있다. 아래 그림은 python.org 출처의 heappush 사용법 예시이다. 튜플의 왼쪽은 비교 대상이 되고, 오른쪽은 실제 값으로 설정을 해서 넣을 수 있다. 

---

코드

import heapq
from sys import stdin

var_N = int(stdin.readline())
heap = []

for _ in range(var_N):
    num = int(stdin.readline())

    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])   # heap 인덱스 1번, 젤 앞의 원소
        else:
            print("0")
    else:
        heapq.heappush(heap,(abs(num), num))  # abs(num)을 보고 heap을 정렬하므로, 정렬은 절댓값으로, 원래값은 그대로 들어가고.

---

마무리

heappush를 튜플로 지정해서 넣을 수 있다가 포인트이다! 또한, 아래 사진처럼, heappush 정의를 따라서 내용을 보았는데, 튜플과 관련해서 내용을 알 수가 없었다. 이런 경우, 추가적으로 org referrence를 참조해보면 정보를 얻을 수 있다는 것을 알게 되었다.