코드

import heapq
n = int(input())

heap = []

for _ in range(n):
    x = int(input())
    
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heap[0])
            heapq.heappop(heap)
    else:
        heapq.heappush(heap, x)

문제 해설

최소 힙에 대한 이해도가 있는가 물어보는 문제이다.

파이썬의 heapq 내장 모듈이 최소 힙 기능을 제공한다. (PriorityQueue도 있으나 heapq가 더 성능상 빠름)

  • 힙
    • 완전 이진 트리를 기본으로 함
    • 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조
    • 최소힙 : 루트가 가장 값이 작은 힙
    • 최대힙 : 루트가 가장 값이 큰 힙
    • 시간 복잡도 : O(logN)
  • 최소 힙 (heapq 내장 모듈) 메소드
    • heappush(list, item) : 힙으로 사용할 list에 item을 삽입
    • heappop(list) : 힙에서 원소 삭제
    • heapify(list) : list를 힙으로 변경

힙 참고 블로그

매우 정리가 잘 되어있는 블로그를 발견하여 링크를 걸어둔다.

댓글남기기

참고