[백준] 1927번, 최소 힙

💡 최소 힙

- 최소 값을 찾아내기 위해서 완전 이진 트리를 사용하여 연산을 처리하는 자료 구조

- 부모 노드가 자식 노드보다 작거나 같다

 

✓ 최소 힙 직접 구현은 아래 블로그를 참고하여 학습했다.

https://velog.io/@gnwjd309/python-heap

[Python] 파이썬 힙(Heap) 사용하기

 

✓ heapq 모듈

- 이진 트리 기반의 최소 힙 자료구조를 제공한다.

- heapq 모듈은 최소 힙(min heap)의 기능만을 동작한다.

- heappush() : 힙에 원소 추가

- heappop() : 힙에서 원소 삭제

 

💡 문제 

 

💡 코드

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

for i in range(n):
    x = int(sys.stdin.readline())

    # x가 0인경우 가장 작은 값 출력
    if x == 0:
        if heap:
            print(heapq.heappop(heap))
        # 배열이 비어 있으면 0 출력
        else:
            print(0)
    # x 가 0이 아닌경우     
    else:
        heapq.heappush(heap, x)

 

💬 마무리

힙에 대한 개념도 잘 알지 못하였으며 heap 모듈을 사용하는 방법은 생각조차 하지 못했다.

이번 문제는 자료구조에 대한 것을 완벽이 이해하고 암기한 상태에서 풀이 가능했던 것 같다.

또한 만약 heap모듈을 잘 알고 있다면 쉽게 풀 수 있는 문제였다.