백준 1927 최소 힙 c++ [컴공과고씨]

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

1927번: 최소 힙

문제를 보고 priority queue를 떠올리면 쉽게 풀리는 문제였다.

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

priority_queue는 default로는 최대값이 root에 있기 때문에 이것을 최소로 바꾸어주기만 하면된다.

 

바꾸는 법은 

벡터 sort와 마찬가지로 해주면되는데 주의할 점은 최소값을 제일 위로 올리기 위해서 벡터와 다르게 a>b로 해주어야한다. 이유는 저 뜻은 a가 root가 되고 b는 다른 수가 된다. 만약 위가 참이면 swap이 일어나게 된다. 그렇기 때문에 root 다른 수보다 클때 swap해주어야하기 때문에 a>b 이렇게 해주면 최소값을 root로 올릴 수 있다.

다른 방법으로는 greater<int>를 해주면된다. 이것도 역시 벡터와는 반대이기 때문에 주의하자

 

단계별 풀이

1. 입력값이 0이 아니면 priority_queue에 넣어주고

2. 입력값이 0이고 priority_queue가 비어있으면 0을 출력

3. 입력값이 0이고 priority_queue 비어있지 않으면 root값을 출력하고 pop()

 

 

전체코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
struct cmp{
    bool operator()(int a, int b){
        return a > b; // 부호 주의 swap이기 때문
    } 
};
int main(){
    ios::sync_with_stdio(false);
    vector<int> result;
    int n, x;
    cin >> n;
 
    priority_queue<int, vector<int>, cmp> q; // 최소값 root에
    for (int i = 0; i < n; i++){
        cin >> x;
        if(x!=0){ 
            q.push(x); // 0아니면 입력값을 넣어주고 
        }else{
            if(q.empty()){ // 비어있으면
                result.push_back(0); // 0 저장
            }else{
                result.push_back(q.top()); // root값 저장
                q.pop(); // root 하나 제거
            }
        }
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
    return 0;
} // 10min