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

 

1) 문제설명

백준 Online Judge 11286번 절댓값 힙

백준 Online Judge 11286번 절댓값 힙

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

11286번: 절댓값 힙

 

2) 아이디어

우선순위 큐를 선언하고 비교 연산자를 호출하여 절댓값이 작은것이 우선순위가 되도록 swap을 하였다.

만약 절대값이 같은 경우, 둘 중 값이 작은 것이 우선순위가 되도록 swap 하였다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

struct cmp {
	bool operator()(int a, int b) {
		if (abs(a) == abs(b)) { // ab의 절대값이 같은 경우
			if (a > b) { // a가 양수 b가 음수일 경우
				return a > b; // true
			}
			else return b < a; // b가 양수 a가 음수일 경우 false
		}
		return abs(a) > abs(b); // 절대값이 작은 순서대로
	}
};

int main() {
	int n;
	priority_queue <int,vector<int>, cmp> pq;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			if (pq.empty()) { // 큐가 비었다면
				cout << 0 << endl; // 0
			}
			else {
				cout << pq.top() << endl;
				pq.pop();
			}
		
		}
		else {
			pq.push(x);
		}
		
		
	}
}

cmp 구조체를 사용하는 것이 편하다.