백준1927 - 최소 힙(heap) Python

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

 

먼저 힙은 이진트리를 기반으로 한 자료구조로 특정한 규칙에 따라 원소들이 정렬되어 있는 자료구조다.

이진트리란, 한 노드가 최대 두 개의 자식 노드를 가질 수 있는 노드로, 이 덕분에 계층적 정렬 저장이 가능하다.

(간단히 [1,2,3] 을 하나의 큐라고 한다면, 중간에 위치한 2는 앞에 1 | 뒤에 3 이라는 자식 노드를 가짐을 의미한다.)

 

자료구조 힙의 경우는, 파이썬에서 heapq라는 내장 모듈을 불러와 사용이 가능하다. 

물론 직접 힙을 구현하여 사용하는 방법도 있겠지만, 비슷한 자료구조인 큐보다는 비교적 사용빈도가 적기에 

해당 포스팅에서는 모듈을 사용한 풀이만 다룬다.

 

heapq를 사용한 힙에서 사용하는 메서드는 여러가지가 있겠지만 대표적으로는 heappush | heappop 가 있다.

그 말마따나 heappush는 힙에 데이터를 추가, heappop은 정렬된 데이터 중 가장 작은 값을 제거하는 역할을 한다.

import heapq

exam = []

# heapq.heappush(list, value)
heapq.heappush(exam, item)

# heappop(list)
heapq.heappop(exam)

이때 heappop 메서드는 파이썬에서 리스트 메서드인 pop과 달리 인덱스를 인자로 받지 않는데, 

이는 heapq가 기본적으로 오름차순의 데이터 정렬을 지원하기 때문이다.

(내림차순 정렬의 경우 음수로 heap에 데이터를 추가하는 방식으로 구현이 가능하다.)

 

따라서, 입력 값이 0이 아닌 경우에는 heappush를 통해 heap에 데이터 추가

입력값이 0 인 경우, heap이 비어있다면 0 | 그렇지 않다면 heappop으로 가장 작은 값을 결괏값 리스트에 담아 반환하면 된다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

import heapq

def solution (data) :
  data.pop(0)
  arr = list(map(int, data))
  heap = []
  result = []

  for v in arr :
    if v != 0 : heapq.heappush(heap,v)
    else :
      temp = heapq.heappop(heap) if len(heap) else 0
      result.append(temp)

  print('\n'.join(map(str, result)))


solution(input_data)

 

참고한 공식 문서

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm