[Algorithm] 백준 11279번: 최대 힙 | 힙큐(heapq) 이용

문제 출처: https://www.acmicpc.net/problem/11279

---

1. 결과

메모리 35124KB, 시간 152ms

2. 풀이

이 문제는 우선순위 큐를 이용해서 풀 수 있는 문제다. 먼저, 우선순위 큐란 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 이야기하는데, 쉽게 보면 자료형에 자료를 저장할 때, 스스로 각 자료에 우선순위를 부여하며 저장하는 것이다. 그리고 자료를 다시 하나씩 출력할 때, 그 우선순위가 높은 것을 먼저 순서대로 출력하는 것인데, 자세한 내용은 아래 링크의 글을 통해 확인할 수 있다.

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

어쨌든 이 문제는 이런 우선순위 큐를 통해 풀 수 있는데, 파이썬에서는 heapq라는 내장 라이브러리로 우선순위 큐를 구현할 수 있다. heapq의 heappush 메서드는 임의의 리스트에 자료를 우선순위를 부여하면서 저장하고, heappop 메서드는 그 리스트에서 우선순위가 가장 높은 자료를 출력한다. 여기서 일반적으로는 값을 오름차순으로 우선순위를 부여하고, 출력할 때는 우선순위가 가장 높은 것, 즉 값이 가장 작은 자료를 pop 한다. 이를 힙에서는 최소 힙이라고 한다. 하지만 이 문제는 최대 힙(값이 큰 것이 우선순위가 높음)을 구현하는 것이다. 이것은 각 자료에 마이너스(-)를 붙여서 양수는 음수로, 음수는 양수로 변환하며 저장하고, 출력함으로써 구현할 수 있다. 1과 2에서 1이 우선순위가 높게 저장되겠지만, 이를 음수로 저장하면 -1, -2이기 때문에 -2가 더 우선순위가 높은 값이 되기 때문이다. 출력할 때 또한 마찬가지다.

이를 구현한 코드는 아래와 같다.

import sys, heapq

def main():
    N = int(sys.stdin.readline())
    hq = []
    for _ in range(N):
        command = int(sys.stdin.readline())
        if command: heapq.heappush(hq, -command)  # 음수로 변환하며 저장
        else: print(-heapq.heappop(hq)) if hq else print(0)  # 음수로 저장됐기 때문에, 출력할 때는 다시 마이너스를 붙여줌
    return

if __name__ == "__main__":
    main()