[백준] 11286번 절댓값 힙

문제: 11286번: 절댓값 힙

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

struct compare {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        // 일단 절댓값을 기준으로 비교, 그 다음 값을 기준으로 비교
        if (a.first == b.first) {
            return a.second > b.second;
        }
        return a.first > b.first;
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    // 최소힙
    // first: 절댓값, second: 값
    priority_queue < pair<int, int>, vector<pair<int, int>>, compare> pq;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        if (num == 0) {
            if (pq.empty())
                cout << 0 << "\n";
            else {
                pair<int, int> min = pq.top();
                pq.pop();
                cout << min.second << "\n";
            }
        }
        else {
            pq.push(make_pair(abs(num), num));
        }
    }

    return 0;
}

 

음.. 그냥 우선순위큐랑 pair 이용하면 쉽게 해결할 수 있는 문제이다.

 

일단 문제에서 원하는 건 절댓값이 작고, 동시에 그냥 원래 값도 작은 값이 제일 먼저 빠져나오는 것이다. 이를 통해 최소힙을 이용해야 한다는 사실을 알 수 있다.

 

절댓값을 기준으로 먼저 비교를 하는데 만약 둘의 절댓값이 같다면 원래 값으로 비교해야 한다. 원래 값을 비교할 때도 더 작은 값을 위로 보내야 한다.

 

그래서 return 의 두 비교 연산자를 똑같은 걸 써줬다.