[Python] BOJ(백준) 11279번 - 최대 힙

링크

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

난이도(solved.ac 참고)

실버2

풀이

Python의 heapq 모듈만 알고 있으면 너무 쉬운 문제이고, 나 또한 그것을 알고 있어서 금방 풀었지만 포스팅을 하는 이유는 최소힙이 아니라 최대힙이므로, 이를 만드는 쉬운 방법을 공유하기 위함이다.

heapq 모듈을 사용하면서 약간의 트릭을 넣음으로써 최대 힙을 구현할 수 있다. heapq.heappush를 할 때 -의 값으로 집어넣는 것이다. 그렇다면, 기본적으로 heapq 모듈은 최소힙을 가정하므로 - 값이 가장 클 수록 상위에 위치하게 된다. 이것을 출력할 때 절댓값만 씌워주면 최대힙과 똑같다. (물론 음수는 들어가지 않는다는 전제하에. 이 문제는 음수는 입력하지 않는다고 했으므로 이렇게 풀 수 있음)