백준 s1 11286 절댓값 힙 c++

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

11286번: 절댓값 힙

 

문제

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

N개의 x가 주어지고, x가 0이면 절댓값이 가장 작은 값을 출력하고 제거, 그렇지 않으면 큐에 x를 넣는다.

 

풀이

priority_queue는 기본적으로 최대 힙이다.

이를 최소 힙으로 바꾸려면 다음과 같이 선언해주면 된다.

//최대 힙
priority_queue<int> pq;
//최소 힙
priority_queue<int, vector<int>, greater<int>> pq;

 

문제에서 구해야할 건 절댓값 순으로 정렬하는 priority queue이므로, compare 함수를 custom해서 써줄 필요가 있다.

priority queue의 custom compare함수는 sort에서 쓰는 것과 약간 다르게 생겼다.

class cmp {
	public:
    	bool operator() (int a, int b) {
        	...
        }
};

 

한 가지 더 유의해야 할 점은 priority queue는 기본적으로 최대 힙이다.

 

compare함수는 (a, b)를 비교할 때 (앞에 있는 수, 뒤에 있는 수) = true 여야 한다.

 

priority queue는 최대 힙이므로 가장 뒤에 있는 원소를 최우선 순위로 한다. 

return a > b에서 b의 우선순위가 더 높다고 해보자.

a > b 에서 b가 더 작아야 뒤로 가므로, b가 더 큰 게 true가 아니라 b가 더 작은 게 true이다.

 

전체 코드

/*boj s1 11286 절댓값 힙*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 105
using namespace std;

int N;

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

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