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

 

설명)

우선순위 큐를 이용하여 풀면 간단하게 풀리는 문제이다. 다만, 이전의 최소힙, 최대힙과 다르게 사용자정의 비교함수를 만들어서 

풀어 주어야한다.

Priority queue의 인자는

1. T: 요소 타입이다. 여기서는 int로 설정하면된다.

2. Container이다.  내부 컨테이너로 기본값은 vector이다.

3. Compare : 정렬기준이다. 기본ㄴ값은 최대 힙으로 이부분을 바꿔서 절대값 힙을 구현할 수 있다.

 

<최대 힙>

우선순위 큐의 경우 최대 힙이 default라고 보면된다. 따라서 코드도 간결하다.

priority_queue<int> pq;

 

<최소 힙>

최소힙의 경우 std::greater<Type>을 Compare로 지정하면된다. 따라서 코드로 적어보면,

priority_queue<int, vector<int>, greater<Type>> pq; 

이런식이 되겠다.

 

<절대값 힙>

그렇다면 이번 문제의 경우 이 Compare 부분을 사용자정의 비교함수를 만드는 것이 이 문제의 핵심이다 

나의 경우 다음과 같이하였다.

 

코드)

전체 코드는 다음과 같다.

#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;

	cin.tie(0);
	ios::sync_with_stdio(0);

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

	while (n--) {
		int n;
		cin >> n;

		if (n == 0) {
			if (pq.empty()) {
				cout << '0' << '\n';

			}
			else {
				cout << pq.top() << '\n';
				pq.pop();

			}
		}
		else {
			pq.push(n);

		}

	}
}