💻 백준 11279: 최대 힙

문제 소개 🧐

N개의 연산이 주어질 때, 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 문제입니다. 만약 배열이 비어있으면 0을 출력합니다.

입력 📝

  • 첫째 줄에 연산의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
  • 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어집니다.
  • x가 자연수이면 배열에 x라는 값을 넣는(push) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는(pop) 연산입니다.

출력 📤

  • 입력에서 0이 주어진 횟수만큼 답을 출력합니다.
  • 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력합니다.

첫 번째 시도: heapq 모듈 활용 🚀

Idea

파이썬의 heapq 모듈은 최소 힙(min heap)을 기본으로 제공해서
이 점을 활용해서 최대 힙(max heap)을 구현해야겠다고 생각했다

가장 간단한 방법은, 힙에 원소를 추가할 때 -1을 곱해서 넣고
반대로 힙에서 원소를 꺼낼 때 다시 -1을 곱해 원래 값으로 되돌리는 방식이었다

이렇게 하면 최소 힙 자료구조를 그대로 사용하면서 최대 힙의 효과를 낼 수 있을거라 판단했다

Code

import heapq
import sys

input = sys.stdin.read
data = list(map(int, input().split()))

heap = []
results = []
n_index = 0
N = data[n_index]
n_index += 1

for _ in range(N):
    x = data[n_index]
    n_index += 1
    if x == 0:
        if heap:
            results.append(str(-heapq.heappop(heap)))
        else:
            results.append("0")
    else:
        heapq.heappush(heap, -x)

print("
".join(results))

Result

  • 성공! 🎉
  • heapq를 이용한 최대 힙의 기본적인 구현 방법을 익힐 수 있었다

개선할 부분 🤔

  • heapq 모듈로 최대 힙을 구현하는 가장 기본적인 방법을 연습할 수 있었다
  • 음수로 변환하는 아이디어는 간단하지만 강력해서 기억해두면 좋을 것 같다
  • 다른 문제에서도 우선순위 큐가 필요할 때 유용하게 사용할 수 있을 것 같다