(C++) - 백준(BOJ) 11286번 : 절댓값 힙 답

www.acmicpc.net/problem/11286

11286번: 절댓값 힙

make_pair를 이용해 priority queue를 사용하는 문제였습니다.

 

풀이방법

 priority queue의 기본 자료구조는(선언시 3번째 인자로 아무것도 설정하지 않거나 less설정을 줬을 때)은 max heap입니다.  이는 priority queue에 들어가는 원소가 pair의 형태를 하고 있어도 같습니다. 따라서 greater로 min heap을 인자로 줌으로써 min heap으로 자료구조를 만들어 줍니다. make_pair함수를 이용해 한 쌍의 원소를 넣는 방법이 있지만 {a,b}의 형식이 더 간편해 후자의 방식을 선택해 구현했습니다. pair<int,int>형태의 자료구조에서 min heap은 첫번째 원소(가장 왼쪽 원소)가 더 작을수록, 첫번째 원소가 같다면 두번째 원소가 더 작은순으로 정렬된 heap구조를 띕니다. 따라서 문제의 조건을 모두 만족할 수 있습니다.

 

Code 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair <int, int> pairs;
int main() {
    fastio;
    int n;
    cin >> n;
    pairs minElement;
    priority_queue <pairs,vector<pairs>,greater<pairs>> pq;
    while(n--){
        int x;
        cin >> x;
        if(!x){
            if(!pq.empty()){
                minElement = pq.top();
                cout << pq.top().second << '\n';
                pq.pop();
            }
            else cout << 0 << '\n';
        }
        else pq.push({abs(x),x});
    }
}