궤도

[백준] 1927번 : 최소 힙 본문

💻 현생/⛓ 알고리즘

[백준] 1927번 : 최소 힙

영이오 2021. 4. 4. 19:21

문제

 


풀이

 

11279번과 마찬가지로 우선순위 큐를 사용하면 된다.

우선순위 큐의 default는 최대 힙이다.

 

우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다.

그럼 그 반대인 greater로 바꿔주면 최소 힙이 되겠다.


소스코드

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    priority_queue<int, vector<int>, greater<int>> pq; //greater면 min heap
    int N, x;

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>x;
        if(x==0){
            if (pq.empty())
                cout<<0<<'\n';
            else{
                cout<<pq.top()<<'\n';
                pq.pop();
            }
        }
        else
            pq.push(x);
    }
}
Comments