[BOJ][Python]1927번 풀이

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

1927번: 최소 힙

import heapq
import sys
input = sys.stdin.readline

n = int(input())
h = []
for _ in range(n):
    order = int(input())
    if order > 0:
        heapq.heappush(h,order)
    else:
        if len(h)==0:
            print(0)
        else:
            print(heapq.heappop(h))

해당 문제를 풀어보기 전에는 힙(heap) 자료구조를 이름만 들어본 정도라서 저는 이 문제를 검색을 해보고 겨우 풀었습니다. 아마 다음에 힙에 대해서 공부를 하고 포스팅을 작성하게 될 것 같은데 일단 힙에 대해서 해당 문제와 관련된 정보만 간략하게 소개해드리겠습니다.

 

힙 자료구조는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 속성의 자료구조라고 합니다. 보통 우리가 최솟값을 찾거나 최댓값을 찾는 과정을 일반적으로 생각해본다면 하나씩 비교해서 가장 큰 것과 가장 작은 것을 고르게 될텐데요. 힙은 트리의 형태로서 부모 노드와 자식 노드가 우선 순위에 따라 연결됩니다. 예를 들어서 숫자가 클 수록 우선순위가 높은 힙을 구성한다고 하면 자식 노드는 무조건 부모 노드보다 값이 작아야 하는 것이죠. 그렇다면 맨 위에 있는 정점이 가장 큰값이 될테니 굳이 다른 자료형처럼 하나하나 비교할 필요없이 트리 제일 위에 있는 값을 바로 쓰면 되겠죠. 이렇게 부모 노드의 값이 항상 자식 노드의 값보다 큰 힙을 '최대 힙' 이라고 부릅니다. 반대로 부모 노드가 자식 노드보다 작은 힙은 '최소 힙'이라고 부르구요.

 

힙의 이러한 특성 때문에 해당 문제처럼 계속해서 최솟값을 출력해야하는 문제나 최댓값을 출력해야하는 문제를 풀 때 단순히 min이나 max를 쓰는 것 보다 힙을 사용하는게 시간복잡도 면에서 훨씬 좋은 프로그램을 짤 수 있겠죠. 실제로 해보시면 ide에서 실행하는 속도가 다른게 체감이 될 정도로 힙이 빠릅니다. 보통 컴퓨터처럼 고사양 cpu가 탑재되어 있으면 아무리 느리다한들 무한 루프를 도는 수준이 아니라면 체감이 잘 안되는데 예제 1번에서도 차이가 확 날 정도로 힙이 빨랐습니다. 오늘 좋은 걸 알아가는 것 같아서 기분이 좋네요.