[Python] 백준 11279. 최대힙

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

11279번: 최대 힙

문제 설명:

단순 알고리즘 적용문제이다. 힙으로 해결 가능하다.

주의 할 점은 파이썬은 힙 모듈은 디폴트가 최소힙으로 되어있다.

 

풀이 설계:

• 0이 입력되었을때 힙이 비어있으면 0을 출력
• 0이 입력되어있을때 힙에 원소가 있으면 출력
• 0이 입력되지 않았으면 heap에 원소추가
  • 이때 제공된 모듈은 최소힙이기때문에 (-1)을 곱해 넣어준다.
    • 5,6,3 -> -6, -5, -3 (6이 꺼내게 될때 다시 (-1)을 곱해주면 최소힙처럼 쓸 수 있다.)

import sys
import heapq

input = sys.stdin.readline
n = int(input())
heap = []

for case in range(n):
    num = int(input())
    if num == 0:
    	#0이 입력되었을때 힙이 비어있으면 0을 출력
        if len(heap) == 0:
            print(0)
        #0이 입력되어있을때 힙에 원소가 있으면 출력
        else:
            print(heapq.heappop(heap)*(-1))
            
	#0이 입력되지 않았으면 heap에 원소추가
	#이때 제공된 모듈은 최소힙이기때문에 (-1)을 곱해 넣어준다
    else:
        heapq.heappush(heap, num * (-1))