백준 11286 c++ "절댓값 힙" -[PlusUltraCode]

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

11286번: 절댓값 힙

 

[필자 사고]

이 문제는 절댓값 힙 문제이다.

 

힙 관련 알고리즘은 우선순위 큐라고 말할 수 있다. 여기서 중요한 포인트는 

 

양수만 주어지는게 아닌 음수 또한 주어지고 그 중 절댓값이 작은 값으로 정렬해야 된다는 점이다.

 

만약 절댓값이 같으면 실제 더 작은값을 정렬해야 된다는 점도 있다.

 

쉽게 말해 우선순위 큐를 이용하여 우선순위 정렬 알고리즘을 직접 작성할 수 있는지 없는지를 물어 보는 문제이다.

 

우선순위의 특이점 때문에 기존 벡터에서 정렬 알고리즘 함수를 작성할 때는

 

return a<b 를 하면 a 에서 b순으로 정렬이 되지만 우선순위에서는 b-> a 로 정렬이 된다. 

 

즉 기존 벡터와 반대로 생각하면 된다.

 

[소스 코드]

 

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

typedef struct Node {
	long num;
};

struct cmp {
	bool operator()(long num1, long num2) {
		if (abs(num1) == abs(num2)) {
			return num1 > num2;
		}

		return abs(num1) > abs(num2);
	}
};

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

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		long number;
		cin >> number;
		if (number == 0) {
			if (pq.empty() == true) {
				cout << 0<<'\n';
				continue;
			}
			cout << pq.top()<<'\n';
			pq.pop();
			continue;
		}

		pq.push(number);


	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	Input();
}