[백준] 11279 최대 힙

문제

www.acmicpc.net/problem/11279

 

 

코드

첫 번째 코드 (시간 초과)

 

아래 코드는 시간 초과가 나는 코드이다. 이유는 input()을 사용했기 때문이다.

시간초과가 나지 않으려면 sys.stdin.readline()을 사용해야 한다고 한다.

from heapq import heappop, heappush

N = int(input())
heap = []
for _ in range(N):
    num = int(input())
    if num == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heappop(heap)[1])
    else:
        heappush(heap, (-num, num))

 

두 번째 코드

from heapq import heappop, heappush
import sys

N = int(sys.stdin.readline())
heap = []
for _ in range(N):
    num = int(sys.stdin.readline())
    if num == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heappop(heap)[1])
    else:
        heappush(heap, (-num, num))

sys.stdin.readline()으로 바꿨더니 바로 정답이 되었다.

 

개념

힙

완전 이진 트리의 일종. 중복 값을 허용한다.

 

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

파이썬 힙 자료구조

• heapq.heappush(heap, item) : item을 heap에 추가 
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.  
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

최대 힙

파이썬의 heapq 모듈은 기본적으로 최소 힙으로 구현되어 있다. (-item, item)의 튜플 형태로 넣어주면 최대 힙 구현이 가능하다.

 

heapq.heappush(max_heap, (-item, item))

 

heap = [1,2,3,4,5]

max_heap = []
for item in heap:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

 

실제 값은 인덱스 1에 저장되어 있으므로 heapq.heappop(max_heap)[1] 을 이용하면 된다.