[c++] 백준 11286 절댓값 힙

백준 단계별로 풀어보기 [우선순위 큐] 절댓값 힙

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

11286번: 절댓값 힙

 

[풀이]

pair를 이용해서 입력된 수와 그 수의 절대값을 모두 큐에 저장한다. 우선순위 큐는 pair의 첫번째 인자를 기준으로 값을 저장하고, 그 값이 같다면 두번째 인자를 기준으로 저장한다. min_heap을 이용하여 절대값이 같다면 더 작은 수를 우선으로 저장해 출력하게 한다. 

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#include <cstdlib>

int main() {
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int n;
	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (a != 0) {
			b = abs(a);
			pq.push(make_pair(b, a));
		}
		else {
			if (!pq.empty()) {
				cout << pq.top().second << "\n";
				pq.pop();
			}
			else 
				cout << "0\n";
		}
			
	}

}