[BOJ/C++] 절댓값 힙(11286번)

1. 개요

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

11286번: 절댓값 힙

1-1. 설명

절댓값 힙은 아래와 같은 연산을 지원하는 자료구조이다.

 - 배열에 정수 x를 넣음

 - 배열에서 절댓값이 가장 작은 값을 출력후 그 값을 배열에서 제거

 - 절댓값이 가장작은 값이 여러개일 경우, 가장 작은 수를 출력하고 그 값을 배열에서 제거

절댓값 힙이 동작하는 프로그램을 작성하라. 

1-2. 제한 사항

 - 첫 줄에 연산 개수 N이 주어지며 N은 1 이상 100,000 이하

 - 다음 N개 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어짐

 - x가 0이 아니라면 배열에 넣고, 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 제거

 - 입력되는 정수는 -2^31이상 2^31 이하

---

2. 구현

2-1. 풀이

우선순위 큐를 통해 구현해주었으며, 비교 연산자를 구현하였다. 여기서 sort 함수와는 다르게 비교 함수가 아닌, 구조체임에 주의하자. 

2-2. 코드

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

struct compare {
    bool operator()(const int a, const int b) {
        if (abs(a) == abs(b)) {
            return a > b;
        }
        else return abs(a) > abs(b);
    }
};

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

    priority_queue<int, vector<int>, compare> que;
    int N, num;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num == 0) {
            if (que.size() == 0) cout << "0\n";
            else {
                cout << que.top() << "\n";
                que.pop();
            }
            continue;
        }
        que.push(num);
    }
    return 0;
}