백준 11279번: 최대 힙

✔ 풀이를 위한 아이디어

• 우선순위 큐 (Priority Queue)와 힙 (Heap)
  
  

✔ 수정 전 코드 [시간 초과]

import sys

N = int(sys.stdin.readline())
Heap = [-1]

for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(Heap) == 1:
            print("0")
        else:
            Heap[1], Heap[len(Heap) - 1] = Heap[len(Heap) - 1], Heap[1]
            print(Heap.pop())
            i = 1
            while True:
                if 2*i < len(Heap)-1:
                    if Heap[i] < Heap[2*i]:
                        Heap[i], Heap[2*i] = Heap[2*i], Heap[i]
                        i = 2*i
                elif 2*i+1 < len(Heap)-1:
                    if Heap[i] < Heap[2*i+1]:
                        Heap[i], Heap[2*i+1] = Heap[2*i+1], Heap[i]
                        i = 2*i+1
                else:
                    break
    else:
        Heap.append(x)
        i = len(Heap) - 1
        while i > 1:
            if Heap[i] > Heap[i//2]:
                Heap[i], Heap[i//2] = Heap[i//2], Heap[i]
                i = i//2
            else:
                break

• 약 1년도 더 전에 (벌써 1년이나 됐어?!) 자료구조 수업 시간에 배웠던 힙 (Heap). 까먹어서 다시 공부하였다. https://chanhuiseok.github.io/posts/ds-4/
• 직접 힙 (Heap) 을 구현해보았지만 백준은 야박하게도 시간 초과를 때려버렸다. 시간 초과 문제를 해결할 방법을 알아보던 중, 파이썬에서 heapq라는 모듈을 지원한다는 것을 알게 되었고, 바로 해당 모듈을 활용하는 쪽으로 코드를 수정하였다.
• 나중에 코딩 고수가 되면 위의 코드를 수정하여서 시간초과가 안나게 해보고 싶다.
  
  

✔ 수정 후 코드

import sys
import heapq

N = int(sys.stdin.readline())
Heap = []

for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(Heap) == 0:
            print("0")
        else:
            tmp = heapq.heappop(Heap)
            print(tmp[1])
    else:
        heapq.heappush(Heap, (-x, x))

• 파이썬에서 지원하는 heapq 모듈을 공부하였다. https://www.daleseo.com/python-heapq/
• 기본적으로 지원하는 heapq 모듈은 최소 힙을 지원하고 있기 때문에, (-x, x)와 같이 튜플 (tuple) 에 넣어서 역순으로 정렬되도록 하고, 출력 할 때는 index 1의 원래 값만 나타나도록 했다.
  
  

• 처음 제출했을 때는 Heap의 크기를 고려하지 않고 2 x i 나 2 x i + 1 같은 값을 참조했다가 indexError가 났었다.
• 이후 Python3와 PyPy3에서 모두 시간초과를 맛보고, heapq 모듈을 사용하는 쪽으로 넘어갔다.

✔ 관련 개념

• 힙 (Heap)과 heapq 모듈의 활용