최대 힙 / 11279 / 실버 2

문제 링크

코드

import heapq
import sys

maxHeap = []

N = int(sys.stdin.readline())

for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(maxHeap) == 0:   # 만약 배열 길이가 0이라면 0 출력
            print(0)
        else:   # 가장 큰 값 pop
            print(heapq.heappop(maxHeap)[1])
    else:   # 배열에 추가
        heapq.heappush(maxHeap, (-x, x))    # heapq는 작은 순으로 정렬되기 때문에 -x로 정렬시킴

정리

시간 초과가 나므로 input() 대신 sys.stdin.readline() 사용

import heapq
heapq.heappush(heap, item) # item을 heap에 추가
heapq.heappop(heap) # heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출
heapq.heapify(x) # 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
#최대힙으로 만들기
#힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.
heapq.heappop(max_heap)[1]

절댓값 힙 / 11286 / 실버 1

코드

import heapq
import sys

maxHeap = []

N = int(sys.stdin.readline())

for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(maxHeap) == 0:   # 만약 배열 길이가 0이라면 0 출력
            print(0)
        else:   # 가장 큰 값 pop
            print(heapq.heappop(maxHeap)[1])
    else:   # 배열에 추가
        heapq.heappush(maxHeap, (abs(x), x))    # heapq는 작은 순으로 정렬되기 때문에 abs로 정렬시킴

정리

직접 프린트해가면서 확인해보니 python의 heapq 모듈에서는, tuple을 heap으로 정렬할 때 첫번째 아이템의 크기 순으로 정렬한 뒤 같으면 두번째 아이템의 크기 순으로 정렬한다.

N번째 큰 수 / 2075 / 골드 5