백준 1927번: 최소 힙

문제

문제 바로가기> 백준 1927번: 최소 힙

풀이 1 - PriorityQueue 라이브러리

첫번째 방법은 이미 구현되어 있는 PriorityQueue 라이브러리를 이용하는 것이다.
이 방법은 thread safe(lock 제공)한 대신 시간이 많이 소요된다는 단점이 있다.

from queue import PriorityQueue : class import
pq = PriorityQueue() : priority queue 생성
pq.qsize() : 큐의 사이즈를 반환
pq.put(x) : x 원소 추가
pq.get() : 원소 삭제 (오름차순)

우선순위큐의 put(), get() 함수 시간 복잡도 : O(log n)

def solution():
    import sys
    from queue import PriorityQueue

    input = sys.stdin.readline
    pq = PriorityQueue()
    n = int(input())
    for i in range(n):
        x = int(input())
        if x==0:
            if pq.qsize()==0:
                print(0)
            else:
                print(pq.get())
        else:
            pq.put(x)
solution()

풀이 2 - heapq 모듈

heapq 모듈은 파이썬의 리스트를 최소 힙처럼 다룰 수 있도록 도와주는데, 이를 사용하면 메모리와 시간을 더 절약할 수 있다.

heapq.heappush(heap, x): heap에 원소 x 추가
heapq.heappop(heap): heap에서 원소 삭제
heapq.heapify(list): 기존 리스트를 heap으로 변환

def solution():
    import sys, heapq
    input = sys.stdin.readline
    heap = []
    n = int(input())
    for _ in range(n):
        x = int(input())
        if x:
            heapq.heappush(heap, x)
        else:
            if len(heap) == 0:
                print(0)
            else:
                print(heapq.heappop(heap))
solution()

c++을 이용한 풀이

priority queue를 이용하여 풀었고, 최소힙으로 만들어 주기 위해 -x를 집어넣고, -top을 출력해주었다.

#include<iostream>
#include<queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    priority_queue<int> pq;
    int n; cin>>n;
    for(int i=0; i<n; i++){
        int tmp; cin>>tmp;
        if(tmp == 0){
            if(pq.empty()) cout << 0 << '\n';
            else {
                int top = pq.top(); pq.pop();
                cout << -top << '\n';
            }
        }
        else pq.push(-tmp);
    }
}