C++ / 백준 / 11286 / 절댓값 힙

문제

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

11286번: 절댓값 힙

문제풀이

compare라는 비교 함수를 정의하여 절댓값이 같으면 가장 작은 수를, 절댓값이 다르면 절댓값이 작은 수 순으로 정렬을 했다.

0을 입력받을 때 우선순위 큐가 비어있으면 0을 출력, 비어 있지 않으면 compare함수로 정렬한 대로 우선순위가 높은 값을 출력하고 pop을 하여 값을 제거한다.

0이 아닌 수를 입력받으면 우선순위 큐에 값을 입력한다.

 

코드

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

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

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

	int N(0), idx(0);
	int num(0);
	priority_queue<int,vector<int>,compare>pq;
	cin >> N;
	for (idx = 0; idx < N; ++idx) {
		cin >> num;
		if (!num) {
			if (pq.empty())
				cout << 0;
			else {
				cout << pq.top();
				pq.pop();
			}
			cout << '\n';
		}
		else {
			pq.push(num);
		}
	}
}