백준 11279 최대 힙 c++ [컴공과고씨]

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

11279번: 최대 힙

priority queue 우선순위 큐를 사용하면 쉽게 풀리는 문제이다.

priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다.

priority_queue는 default로는 최소값이 root에 있기 때문에 이것을 그대로 사용해주면 된다.

 

 

전체코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    vector<int> result;
    int n, x;
    cin >> n;
 
    priority_queue<int> q;
    for (int i = 0; i < n; i++){
        cin >> x;
        if(x!=0){
            q.push(x);
        }else{
            if(q.empty()){
                result.push_back(0);
            }else{
                result.push_back(q.top());
                q.pop();
            }
        }
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
        return 0;
}