Algorithm/Baekjoon

[Baekjoon, C++] 11279번 : 최대 힙

JMcunst 2021. 2. 16. 12:26
728x90
반응형

도입

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

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

백준 11279번 입출력 예제 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)

코드

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,[-num,num])  # -num 은 우선순위, num은 원소값

마무리

우선순위큐의 첫 번째 문제였다. 첫 번째 문제여서 알고리즘의 난이도 보다는, 새로운 자료구조에 대한 학습이 필요한 파트였다. 

728x90
반응형