백준 1927 - 최소 힙

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

1927번: 최소 힙

트리 형태의 자료구조 중 제일 쉽고 간단(?)한 힙 자료구조의 가장 쉬운 문제다. 사실 우선순위 큐로 설명이 되긴 하지만... 일단 보이기에는 트리처럼 보이니까.

 

힙의 특징으로는

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
    간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다.
  
  

파이썬에는 힙 자료구조 구현을 위해 heapq 라는 모듈을 제공한다.

heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다.  그러므로 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘긴다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이다.

 

원소를 집어넣을 때는 heapq.heappush(list, element) 의 형태로 집어넣고, 원소를 뺄 때에는 heapq.heappop(element)의 형태로 진행된다. 문제에서 원하는 형태로 코드를 짜 보면

import sys, heapq

input = sys.stdin.readline

heap = []
n = int(input())
for i in range(n):
    num = int(input())
    if num==0:
        if len(heap)<1:
            print(0)
        else:
            exit = heapq.heappop(heap)
            print(exit)
    else:
        heapq.heappush(heap, num)

의 형태로 코드를 짤 수 있다.

heap의 요소가 없을 때에도 0이 입력되는 경우가 있으므로 len(heap)<1이면 무조건 0을 출력하고 heap에 요소가 있으면 heappop을 진행하도록 한다.