[파이썬] 11279번 '최대 힙' 문제 풀이

[파이썬] 11279번 '최대 힙' 문제 풀이

heapq모듈은 기본적으로 최소 힙만 지원하기 때문에 주어진 데이터들을 음수로 바꾸고 최소 힙으로 차례대로 값을 추출한 후 다시 양수로 바꾸는 과정을 거쳐 최대 힙을 이용한 연산과 같은 결과로 유도하여 해결합니다.

데이터 1, 4, 3, 6, 2, 5를 최소 힙을 사용하여 내림차순 정렬하는 과정

[1, 4, 3, 6, 2, 5] → [-1, -4, -3, -6, -2, -5] → [-6, -5, -4 , -3, -2, -1] → [6, 5, 4, 3, 2, 1]

최소 힙에 값을 삽입하고 추출할 때 어떠한 과정을 거쳐 최솟값이 나오는지에 대한 설명

https://lbdiaryl.tistory.com/152?category=1015060

풀이

import sys import heapq input=sys.stdin.readline N = int(input()) heap = [] for _ in range(N): num = int(input()) if num==0: if len(heap)==0: print(0) else: print(-heapq.heappop(heap)) else: heapq.heappush(heap, -num)

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

from http://lbdiaryl.tistory.com/182 by ccl(A) rewrite - 2021-10-18 11:01:07