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

문제

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

 

 

 

풀이

제목 그대로 최대 힙 자료구조를 사용하는 문제이다.

최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 완전 이진 트리로 구현된 자료구조이고

따라서 최대힙의 Root 노드에는 항상 전체 트리의 최대값이 저장된다.

 

파이썬은 편리하게도 heapq 모듈을 import하면 최소 힙 자료구조를 사용할 수 있지만,
애석하게도 최대 힙은 구현이 되어있지 않은데, 모든 값에 -를 붙여서 뒤집으면 최소힙을 최대 힙처럼 사용이 가능하다.

(마이너스를 붙여서 야매로 뒤집는건 최대 힙 말고도 내림차순 정렬 할때도 유용하다.)

 

heap 모듈은
힙으로 사용할 빈 리스트를 선언하고 
heapq.heappush(리스트, 값)으로 값을 push하고
heapq.heappop(리스트)로 Root노드의 최소 값을 pop하다. 간단하다.

 

 

 

 

최소 힙 문제의 정답 코드에 마이너스 기호를 딱 두개 추가하면 된다.

정답 코드

import heapq
import sys
input = sys.stdin.readline

N = int(input())
minHeap = []
for _ in range(N):
    x = -int(input())
    if x == 0:
        print(-heapq.heappop(minHeap) if minHeap else 0)
    else:
        heapq.heappush(minHeap, x)