[Baekjoon] 11286번: 절댓값 힙

🥅 문제

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

 

🔍 설계

우선순위 큐를 사용하여 첫 번째 조건으로 절댓값을 비교하고, 두 번째 조건으로 절댓값이 같다면 실제 값을 비교하여 작은 것이 우선순위가 높도록 한다.

 

👊 풀이

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

int n, x;

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

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


int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (x == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(x);
		}
	}
	return 0;
}

 

📝 메모

우선순위 큐의 compare는 구조체로 만들어서 사용하며, 배열에서 정렬하는 함수와 반대로 생각해야 한다.