[백준/C++] 11286번: 절댓값 힙

문제

해설

절대값 힙이라는 자료구조를 우선순위 큐로 만들어 구현했습니다.

c++의 우선순위 큐는 가장 큰 값이 출력이 되는데, 절댓값이 가장 작은 값을 출력해야기에 -를 붙혀 push하였습니다.

그리고 연산자 오버로딩으로 절댓값이 같을 때 더 작은 수를 출력하도록 했습니다.

코드

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

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

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

	priority_queue<int, vector<int>, cmp> pq;

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int x; cin >> x;

		if (x != 0) {
			pq.push(-x);
		}
		else {
			if (pq.empty()) cout << 0 << '\n';
			else {
				cout << -pq.top() << '\n';
				pq.pop();
			}
		}
	}

	return 0;
}