[Python] BOJ/백준 11279번 최대 힙

[문제]

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

11279번: 최대 힙

 

[풀이]

이전 글의 최소 힙과 같이 파이썬의 heapq 모듈을 사용하나, 해당 모듈은 최소 힙 기능만 동작하기 때문에 최대 힙으로 활용하기 위해서는 조금의 조작이 추가로 필요하다.

2021.08.28 - [BOJ] - [Python] BOJ/백준 1927번 최소 힙

[Python] BOJ/백준 1927번 최소 힙

 

최대 힙을 만들기 위해서는 각 값에 대한 우선순위를 구한 후, (우선순위, 값) 구조의 튜플을 힙에 추가하거나 삭제하면 된다. 힙에서 값을 읽어올 때에는 우선순위는 필요 없기 때문에 각 튜플의 인덱스 1에 있는 값만 읽으면 된다.

heapq.heappush(heap, (-num, num))

위 코드에서 (-num, num) 처럼 (우선순위, 값) 의 튜플 형태로 저장한다.

 

print(heapq.heappop(heap)[1])

우선순위는 출력에 필요 없기 때문에 인덱스 1 값만 읽어온다.

 

[코드]

import sys
import heapq

if __name__ == '__main__':
    heap = []
    for _ in range(int(sys.stdin.readline())):
        x = int(sys.stdin.readline())
        if x == 0:
            if not heap:
                print(0)
            else:
                print(heapq.heappop(heap)[1])
        else:
            heapq.heappush(heap, (-x, x))