[백준][C++] 11286: 절대값 힙

 

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

11286번: 절댓값 힙

 

 

 

 

 

---

- 문제

 

  주어진 수를 우선순위 큐에 넣고 절대값이 작은 수 부터 출력하는 문제다.

 

 

---

- 해설

우선순위 큐를 사용하기 위해 비교연산자를 만들 필요가 있다.

 

struct cmp로 만들고 아래에 bool operator()를 오버로하여 만든다.

 

a > b의 형태로 만들었기에 우선순위로 작은 수를 먼저 잡게 되고, < 형식으로 만들면 출력할 때 큰 수부터 나온다.

 

 

 

---

- 풀이

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

struct cmp // 우선순위 큐를 위한 비교연산자
{
    bool operator()(int a, int b)
    {
        if (abs(a) == abs(b)) // 절대값이 같으면
        {
            return (a > b ? true : false); // 작은 수 우선
        }
        return abs(a) > abs(b); // 이것도 똑같이 절대값이 작은 수 우선
    }
};

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

    int N;
    long long x;
    priority_queue<long long, vector<long long>, cmp> pq; // 우선순위 큐를 사용하기 위해 <자료형, 구현체, 비교연산자>를 지정한다. 지정하지 않으면 가장 큰수를 먼저 출력하는 형식
    cin >> N;

    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;
}

 

 

---

- 새롭게 알게 된 점

- 우선순위 큐 비교연산자 적용법