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

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

11286번: 절댓값 힙

---

 문제 풀이

우선순위 큐의 힙 구조를 이용해서 빠르게 정렬을 하는 것이 포인트이다!

절댓값과 일반 값 모두 따져야 해서 pair 구조를 이용했고 내부적으로 정리하기 위해서 구조체를 구현했다!

 느낀 점

그렇게 어렵지 않은 문제인데 오랜만에 코딩을 하다 보니까 많이 버벅거렸다. 꾸준히 계속 연습해야겠다.

 코드

#include <iostream>
#include <queue>
#include <math.h>

using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second < b.second)
			return false;
		else if (a.second == b.second)
			return a.first > b.first;
		else
			return true;
	}
};

int n;
priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq; // <기본, 절대값>

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	
	while (n--) {
		int tmp;
		cin >> tmp;
		
		if (tmp == 0) {
			if (pq.empty())
				cout << 0 << "\n";
			else {
				cout << pq.top().first << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(make_pair(tmp, abs(tmp)));
		}
	}
}