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

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

 

 

[필자 사고]

1. 절대값이 작은 숫자를 출력해라

2.절대값이 같으면 실제로 더 작은 숫자를 출력해라.

즉 우선순위를 결정하라 라는 뜻이다.

 

필자는 우선순위 큐를 이용해 우선순위 조건을 따로 작성하여 문제를 해결 했다.

보통 우선순위큐에서 우선순위를 정하는 방법은 vector에서 우선순위를 정하는 방식의 반대라 생각하면 된다.

 

실제로 vector에서 우선순위 조건을 결정할 때는

a<b  라는 방시으로 return 하게 될 경우 1,2,3,4, 오름차순으로 정렬된다.

 

반면에 우선순위 큐는 a>b 라는 방식으로 작성해야 오른차순으로 정렬된다.

 

[소스 코드]

 

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>


using namespace std;

struct cmp {
	bool operator()(int a, int b) {
		//절대값이 작은거
		//같은 절대값이라면 실제로 숫자가 더 작은거
		if (abs(a) == abs(b)) {
			return a > b;
		}

		return abs(a) > abs(b);
	}
};

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

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		if (num == 0) {
			if (pq.size() == 0)cout << 0 << '\n';
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
			
		}
		else {
			pq.push(num);
		}
	}
}

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

}