백준 11286. 절댓값 힙 (우선순위큐)

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

11286번: 절댓값 힙

문제를 보면 떠올릴수 있는 풀이가 1) 이진검색트리 2) 우선순위 큐이다. 

우선순위큐가 이진검색트리보다 빠르다. 따라서, 가장 큰값 작은 값을 찾고, 값을 지우거나 넣는 연산만 있다면, 우선순위 큐를 쓰는게 좋다.

(n번째로 큰수를 찾아라, upper_bound, lower_bound를 사용해야한다면 이진검색트리사용)

 

사실 내가 이 문제를 따로 정리하는 이유는 우선순위큐에서 내림차순을 위한 operator()를 만들때, 

기존의 vector, multiset등을 만들때의 bool cmp()와 결과값이 반대이기 때문이다. 

 

설명은 다음 블로그를 참고했다. https://huilife.tistory.com/entry/C-Priority-Queue%EC%9D%98-custom-sort

핵심은 priority queue의 top원소는 container의 back에 있는 원소라는 것이다. 

따라서, 내림차순 정렬했을 때 가장 마지막 원소가 가장 큰 원소여야 한다. 

내림차순으로 정렬 할 때는 앞의 원소가 뒤의 원소보다 크다면 false를 린턴하여 앞의 원소를 뒤로 보내야한다.  

나는 이 부분을 모르고 있어서, 아래의 2번 풀이를 이해하는데 한참걸렸다. 

 

1. 우선순위큐 pair<int, int>사용 풀이법

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

int n;
int x;
int main()
{       
    cin >> n;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> _pq; // 내림차순 정렬
    while(n--)
    {
        cin >> x;
        if(x == 0)
        {
            if(_pq.empty()) cout << 0 << '\n';
            else
            {
                cout << _pq.top().second << '\n';
                _pq.pop();
            }
        }
        else 
        {
            if(x < 0)
                _pq.push(make_pair(x*(-1), x));
            else
            {
                _pq.push(make_pair(x, x));
            }
        }
    }

}

 

2. 우선순위큐 int 풀이법

#include <bits/stdc++.h>
using namespace std;

class cmp {
public:
  bool operator() (int a, int b) {
    if(abs(a) != abs(b)) return abs(a) > abs(b);
    return a > b;
  }
};

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  priority_queue<int, vector<int>, cmp> pq;
  int n;
  cin >> n;
  while(n--){
    int x;
    cin >> x;
    if(x == 0){
      if(pq.empty()) cout << "0\n";
      else{
        cout << pq.top() << '\n';
        pq.pop();
      }
    }
    else pq.push(x);
  }
}

 

3. 이진검색트리 multiset 사용 풀이법

#include <iostream>
#include <stdlib.h>
#include <set>
using namespace std;

//이진검색트리
int n;
int x;

class cmp
{
public: 
    bool operator() (const int a, const int b)
    const{
        if(abs(a) != abs(b)) return abs(a) < abs(b);
        else return a < b;
    } 
};

int main()
{       
    cin >> n;
    multiset<int, cmp> _ms; 

    for(int i = 0; i < n; i++)
    {
        cin >> x;
        if(x == 0)
        {   
            if(_ms.empty()) cout << "0\n";
            else 
            {
                cout << *_ms.begin() << '\n';
                _ms.erase(_ms.begin());
            }
        }
        else
        {
            _ms.insert(x);
        }
    }

}