[백준 1927번 C++] 최소힙

1927번: 최소 힙 (acmicpc.net)

1927번: 최소 힙

---

그렇다.. prioriy_queue를 사용하면 최대 힙이 기본적으로 작동하는 자료구조를 이용할 수 있다

 

[C++] <queue> 라이브러리, 우선순위 큐, 최대 힙, 최소 힙 :: Feel Coding (tistory.com)

[C++] <queue> 라이브러리, 우선순위 큐, 최대 힙, 최소 힙

 

다만 여기서 기본 값이 최대 힙이니까, 방향을 오름차순으로 바꿔주면 최소힙을 구현할 수 있음

값이 작을 수록 우선순위가 높은 우선순위 큐 

를 만드는 것

priority_queue<int, vector<int>, greater<int>> q;

여기서 less가 오름차순으로 방향을 바꿔주는 것!

---

사실 시간초과 났었는데

입출력 시간을 줄여주는 제일 첫 두 줄을 추가해주니까 해결됐다

이제는 잊지말고 이거 계속 써야지 .. 

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

int main()
{
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
    int n, m;
    cin >> n;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0; i<n; i++){
        cin >> m;
        
        if(m == 0){
            if(pq.empty()) cout << 0 <<"\n";
            else {
                cout <<pq.top() <<"\n";
                pq.pop();
            }
        }
        else {
            pq.push(m);
        }
    }
    return 0;
}