백준11279(파이썬) - 최대 힙

www.acmicpc.net/problem/11279

11279번: 최대 힙

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 

힙 (heap): A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

import heapq 를 사용해서 라이브러리를 사용한다.

 

import sys
import heapq
input = sys.stdin.readline

#시간초과 코드(어쩐지 너무쉬웠다)
n = int(input())
number = []
""" for i in range(n):
    a = int(input())
    number.append(a)
    if a == 0:
        print(max(number))
        del number[number.index(max(number))] """

for i in range(n):
    a = int(input())
    heapq.heappush(number,(-a,a))
    if a == 0:
        print(heapq.heappop(number)[1])

기본적으로 heapq.heappop은 최소힙을 기준으로 하기 때문에 최대힙을 구현하기 위해 생각해보았다.

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.  이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대힙으로 사용한다.

 heapq.heappush(number,(-a,a))