[백준] 11286.cpp : 절댓값 힙

www.acmicpc.net/problem/11286

11286번: 절댓값 힙

#include <iostream>
#include <queue>

using namespace std;

int abs(int n) { return n >= 0 ? n : -n; }          // 절댓값 반환 함수

struct cmp
{
    bool operator()(const pair<int,int>& a, const pair<int,int>& b)
    {
        if(a.first == b.first)                      // 절댓값이 같을 경우에는
        {                                           // 원값을 기준으로 오름차순 정렬
            return a.second > b.second;
        }
        else return a.first > b.first;              // 그 외에는 절댓값 기준 정렬
    }
};

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

    int n;
    cin >> n;
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; // 우선순위 큐 선언
    for(int i = 0 , data ; i < n ; i++)
    {
        cin >> data;
        if(data == 0)
        {
            if(pq.empty()) cout << 0 << '\n';
            else
            {
                cout << pq.top().second << '\n';
                pq.pop();
            }
        }
        else
        {
            pq.push(pair<int,int>(abs(data), data));
        }
    }
}

 

[Approach]

1. 우선순위 큐를 활용하는데, 데이터를 페어<절댓값, 원값> 으로 저장하고, 정렬 기준은 절댓값 -> 원값 두개를 거쳐서 정렬해준다.

 

[Point]

1. 우선순위 큐의 정렬 구조체를 선언하는 방법을 익히게 하는 문제인 것 같다.

2. 알고리즘의 sort 정렬과는 다르게 a < b 로 하면 b 가 더 앞으로 땡겨지게 된다. 컨테이너를 벡터로 하든 덱으로 하든 상관 없이.

     정렬의 경우에는 a < b 로 하면 오름차순 정렬이었는데. 정렬 원리가 궁금하다

 

[More]

1. 우선순위 큐에서 컨테이너 벡터 vs 덱, 어떤 차이?