[백준 11279 파이썬] 최대 힙 (실버2, 우선순위 큐)

알고리즘 유형 : 우선순위 큐(최대 힙)
풀이 참고 없이 스스로 풀었나요? : △

https://www.acmicpc.net/problem/11279

소스 코드(파이썬)

import sys
import heapq
input = sys.stdin.readline

max_heap = []

for _ in range(int(input())):
    n = int(input())
    
    if n == 0:
        if max_heap:
            print(-1*heapq.heappop((max_heap)))
        else:
            print(0)
    else:
        heapq.heappush(max_heap, -n)

풀이 요약

1. 최소 힙 모듈 heapq를 약간의 트릭과 함께 활용하면 되는 간단한 문제이다.

   우선순위 큐는 파이썬에서 heapq 모듈(priorityQueue 클래스보다 속도 빠름)로 구현할 수 있는데, 힙에 대해 잘 모른다면 이 곳을 참고하자.

2. 들어오는 수를 리스트에 heappush으로 계속 넣어주는데, 이 때 마이너스를 붙혀서, 실제 우선순위와 반대로 들어가게 한다. 그리고 꺼낼 때는 heappop으로 꺼낸 값에 다시 마이너스를 붙혀서 원래 값으로 꺼내준다. 예를 들어 1, 2, 9를 넣어야될 때, 마이너스를 붙혀서 넣으면 heapq는 최소 힙이므로 나중에 꺼낼 때 -9, -2, -1 순으로 나온다. 다시 마이너스를 붙혀주면 9, 2, 1 순으로 나오게 되는거니 최대 힙의 기능을 수행하는게 된다.

배운 점, 어려웠던 점

• 힙 자료구조에 대해 배웠다. 개념을 공부하고, 직접 메소드 함수를 구현해보면서 원리를 익혔는데 시간을 좀 들였다.

• 바로 print하지 않고, result = ""에 리턴값을 붙혀서 마지막에 한꺼번에 출력하도록 했었는데, 자꾸 WA떠서 그냥 print로 바꿔서 제출했는데, 왜 안되는 풀이인지는 잘 모르겠다...