[백준/python] #11279 최대 힙

future0610 2024. 2. 12. 00:28

문제

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

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

Algorithm

자연수 x를 최대 힙을 사용해 저장한다. 파이썬에서는 최소 힙만 지원하므로 -1을 곱해서 저장하고 출력할 때는 다시 -1를 곱해서 출력한다.

Code

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())

h = []
for _ in range(N):
    x = int(input())
    if x == 0 and len(h) > 0:
        print(-1 * heappop(h))
    elif x == 0 and len(h) == 0:
        print(0)
    else:
        heappush(h, -1 * x)

저작자표시 (새창열림)