[백준 1927] 최소 힙

1. 문제

www.acmicpc.net/problem/1927

1927번: 최소 힙

2. 접근 방법

최소 힙을 느낄 수 있는 문제입니다.

너무 오랜만에 써서 정리할 겸사겸사 사부작사부작 적어보겠습니다.

 

일단 heapq모듈을 사용했습니다.

heapq를 사용하면 최소 힙을 만들 수 있습니다.

 

heapq.heappush(원소를 추가할 대상 리스트, 추가할 원소)

heapq.heappush(원소를 추가할 대상 리스트, 추가할 원소)

를 사용하면 힙에 원소를 추가할 수 있습니다.

 

이 때, 내부적으로 이진트리에 원소를 추가하기 때문에 시간 복잡도는 O(logN)입니다.

 

heapq.heappop(원소를 삭제할 대상 리스트)

heapq.heappop(원소를 삭제할 대상 리스트)

을 이용하면 원소를 삭제할 수 있습니다.

 

이 또한 내부적으로 이진트리를 사용하여 원소를 삭제하기 때문에 O(logN)의 시간 복잡도를 가집니다.

 

+ 참고

- 최소값을 삭제하지 않고 얻는 방법 : 힙리스트의 0번째 인덱스에 접근하면 된다. (ex, 리스트 이름이 heap일 때 heap[0])

- 하지만 두번째로 작은 원소 값의 경우 heap[1]이 아니라 heappop(heap)을 통해 최소값을 삭제하고 heap[0]을 통해 새로운 최소값에 접근해야합니다.

 

- 기존 리스트를 힙으로 변환하고자 할 경우에는

arr = [4, 1, 2, 3]

heapq.heapify(arr)

arr = [4, 1, 2, 3]
heapq.heapify(arr)
print(arr)
# [1, 2, 3, 4]

를 사용하시면 됩니다.

-> 이 경우, 리스트 내부의 원소들이 최소 힙 구조에 맞게 재배치 됩니다.

비어있는 리스트를 생성한 후 heappush()함수를 통해 원소를 하나씩 추가한 효과입니다. -> 따라서 O(N)의 시간 복잡도를 가집니다.

 

3. 코드

python

import heapq, sys

arr = []
N = int(input())
i = 0
while i < N:
    n = int(sys.stdin.readline())
    if n:
        heapq.heappush(arr, n)
    else:
        if arr:
            print(heapq.heappop(arr))
        else:
            print(0)
    i += 1

4. 마치며

참고로 이 문제는 sys.stdin.readline()을 사용할 경우 시간 초과가 납니다요

 

 

출처 : www.daleseo.com/python-heapq/