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

문제 링크

11286번: 절댓값 힙

풀이

커스텀 우선순위 큐를 이용하는 문제

1. 기본적으로 우선순위 큐는 내림차순 정렬이기 때문에 커스텀으로 바꿔줘야한다.
2. 우선순위 큐 커스텀 함수 compare 내부
   2-1. 절댓값이 같으면 작은 것을 앞에 오게 (음수가 양수 앞으로 오게)
   2-2. 절댓값이 작은 것이 앞에 오게
3. 우선순위 큐의 사이즈가 0이면 0 출력
   3-1. 아니라면 pq.top()을 출력 하고, pq.pop()을 해준다.

코드

#include <iostream>
#include <queue>

using namespace std;

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

int main()
{
	int n;
	cin >> n;

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

	for (int i = 0;i < n;i++) {
		int tmp;
		cin >> tmp;
		if (tmp != 0) pq.push(tmp);
		else {
			if (pq.size() == 0) cout << "0\n";
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
	}

	return 0;

}