[Baekjoon, Python] 1927번 : 최소 힙

도입

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

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

---

백준 1927번 입출력 예제 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. heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다. 다시 말해, 우선순위를 따로 지정하지 않아도 된다. 

---

코드

import heapq
from sys import stdin

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

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

    if x != 0:                        #heap에 자연수 x값 넣기
        heapq.heappush(heap, x)
    else:                               #x에 0을 넣었을 경우
        if heap:                        #heap이 비어있지 않았다면,
            print(heapq.heappop(heap))   # heap 인덱스 1번, 젤 앞의 원소
        else:
            print(0)

---

마무리

최대힙과 마찬가지로, heap의 구조와 우선순위큐 자료구조를 알고 있는 상태라면, heapq를 이용한 라이브러리를 활용해서 쉽게 풀 수 있는 문제였다.