티스토리 뷰

728x90
반응형

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

 

11279번: 최대 힙

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

www.acmicpc.net

 

 

 

내 풀이

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 모듈

heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공합니다. 자바의 PriorityQueue 클래스와 비슷하다고 생각하시면 될 듯 합니다.min heap에서 가장 작은 값은 언제나 0번 인덱스(이진 트리

velog.io


다른 사람 풀이

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()

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

반응형
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함