백준 11279번 - 최대 힙

윤여준·2022년 5월 16일
0

백준 풀이

목록 보기
6/35
post-thumbnail

문제

문제 링크 : https://www.acmicpc.net/problem/11279

풀이

heapq 모듈을 사용해서 풀었다.

하지만 heapq에서는 최대 힙을 제공하지 않는다. 그래서 부호를 바꿔서 push를 하고 pop을 하고 나서 다시 부호를 바꾸는 식으로 최대 힙을 구현했다. 음수를 크기가 작은 순서대로 정렬하면 절댓값이 큰 수가 앞으로 오기 때문에 나중에 부호만 바꿔주면 크기가 큰 순서대로 정렬이 된 것과 마찬가지이다.

from sys import stdin
import heapq

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

for _ in range(n):
    x = int(stdin.readline())

    if x == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(-heapq.heappop(heap))
    else:
        heapq.heappush(heap,-x)
profile
Junior Backend Engineer

0개의 댓글