BOJ11279 최대 힙

문제

BOJ11279 최대 힙
실버II | 백준 11279 | Python3 파이썬 풀이

알고리즘

힙은 각 값에 우선순위가 매겨진 특수한 자료 구조이다.

기본 힙 자료구조는 값이 작은 값이 우선순위가 높지만, 이 문제에서는 값이 클수록 우선순위가 높다.

대소 함수를 사용해서 큰 값을 우선순위가 높도록 해줄 수 있지만, 그냥 간단하게 값에 -1을 곱해 대소가 반대대되록 하였다.

즉, 모든 수는 부호가 반대가 되므로 우선 순위가 뒤집히게 된다.

출력할 때는 다시 -1을 곱해서 출력한다.

시간 복잡도
sort()의 경우 최고 $O(N \log N)$, 최악 $O(N^2)$이다.
Heap (Priority Queue)의 경우 push와 pop이 모두 $O(\log N)$이다.

for loop : $O(N)$

즉, sort()를 사용하는 경우 최고 $O(N^2 \log N)$, 최악 $O(N^3)$이지만,
Heap이나 Priority Queue를 사용하면 시간 복잡도가 $O(N \log N)$이 된다.

코드

import sys
import heapq

input = sys.stdin.readline
hq = []

N = int(input())

for n in range(N):
    x = int(input())
    
    if x == 0:
        if len(hq) == 0:
            sys.stdout.write('0\n')
        else:
            sys.stdout.write(str(-heapq.heappop(hq)) + '\n')

    else:
        heapq.heappush(hq, -x)

결과