[CodingTest] 백준 #11279 최대 힙 / 힙큐 heapq

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

11279번: 최대 힙

 

 

 

내 풀이

import sys
import heapq
arr = []
for _ in range(int(sys.stdin.readline())):
    x = int(sys.stdin.readline())
    #(iterator,(우선순위, 넣을 값))
    if x!=0:
        heapq.heappush(arr,(-x,x))
    else:
        if arr:
            num = heapq.heappop(arr)
            print(num[1])
        else:
            print(0)

 

heapq의 heappush는 기본적으로 최소힙으로 이루어져있기 때문에 최대 힙을 구현하기 위해서는 우선순위도 지정해주어야 한다.

따라서, 우선순위를 -x로 지정하면 최대힙 구현이 가능하다.

---

힙큐 관련 자료 (시간복잡도)

https://velog.io/@sossont/Python-heapq-%EB%AA%A8%EB%93%88

[Python] heapq 모듈

---

다른 사람 풀이

import io
import os
import sys
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


def solve():
    q = []
    res = []
    for _ in range(int(input())):
        if (a := int(input())):
            heapq.heappush(q, -a)
        else:
            res.append(-heapq.heappop(q) if q else 0)
    sys.stdout.write('\n'.join(map(str, res)))


if __name__ == '__main__':
    solve()

정수인지 판별할 때 이런 코드를 쓸 수 있다는 것도 꺠달았다.