절댓값 힙

문제: 절댓값 힙 (백준 11286번)

구조 분석

해당 문제 역시 priority queue를 이용하여 heap을 구현하는 문제이다. 다만 이전의 오름차순이나 내림차순 이외의 조건이 붙어서 해당 조건을 위한 비교연산자를 생성해줘야 한다.

풀이 방법

비교 연산자를 활용하여 priority queue를 생성한다.

// return a > b --> 작은 수 부터 출력
// return a < b --> 큰 수 부터 출력
typedef struct cmp {
    bool operator() (int a, int b) {
        return a > b;
    }
} cmp;

priority_queue <int, vector<int>, cmp> pq;

코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int n;
typedef struct cmp {
    bool operator() (int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b;
        }
        else {
            return abs(a) > abs(b);
        }
    }
} cmp;

priority_queue<int, vector<int>, cmp> pq;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    int x;
    for (int i=0; i<n; i++) {
        cin >> x;
        if (x == 0) {
            if (pq.empty()) {
                cout << 0 << "\n";
            }
            else {
                cout << pq.top() << "\n";
                pq.pop();
            }
        }
        else {
            pq.push(x);
        }
    }
    return 0;
}  

정리

해당 문제는 주어진 조건대로 힙 정렬을 실시하는 문제였다. 비교 연산자를 생성하여 힙 정렬을 하는 방법을 알아두자.