백준 1927번 최소 힙 파이썬 문제풀이

문제 링크 : www.acmicpc.net/problem/1927

1927번: 최소 힙

---

힙이란?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다

- 위키백과 출처

 

---

문제해설

최소 힙은 부모 노드가 자식 노드보다 작거나 같은 조건을 만족하는 힙을 의미한다. 

 

새로운 노드를 추가할 때는 트리의 제일 마지막에 노드를 넣은 후 부모 노드가 자식 노드보다 작아질 때까지 부모 노드와 자식 노드를 서로 교환하면 된다.

 

최솟값을 출력하고 싶을 땐 제일 앞에 있는 노드를 빼내고, 가장 마지막에 있는 노드를 최상단으로 올려 자식 노드와 비교해가며 노드를 아래로 내리면 된다.  

 

---

정답 코드

 

사실 이건 실제로 힙을 직접 구현 해 본거고 파이썬엔 최소 힙 자료구조가 이미 존재한다.

풀이시간도 더 적게 걸리고 최대 힙 같은 경우 숫자만 음수로 집어넣어서 사용하면 된다!

import heapq
import sys

input = sys.stdin.readline
#heapq 모듈은 파이썬의 리스트를 최소힙으로 사용할 수 있게 해줌, 새로운 자료구조를 생성하는게 아님에 주의!
MinHeap = []

c = int(input())

for _ in range(c):
	command = int(input())
    if command == 0:
    	#힙에서 최솟값을 빼고 싶으면 heapq.heappop(list)를 사용하면 됨
    	heapq.heappop(MinHeap)
    else:
    	#힙에 노드를 넣고 싶으면 heapq.heappush(list,node)를 사용하면 됨
    	heapq.heappush(MinHeap,command)

---