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

✏️ 문제 링크

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

11286번: 절댓값 힙

 

✏️ 문제 설명

   

✏️ 문제 풀이

     큐 중에서도 우선순위 큐를 이용해서 푸는 문제 

     우선순위 큐를 생성하고 compare구조체를 만들어서 조건에 맞게 출력하도록 해야함

      1. x가 0인 경우

         if(큐가 비어있지 않다면)
           절댓값이 가장 작은 값을 => 같은 게 있다면 음수를 출력 그리고 그 값을 제거

         if(큐가 비어있다면) 0을 출력
      2. x가 0이 아닌 경우 : x를 삽입 => 우선순위 큐와 compare에 의해 자동으로 정렬

 

✏️ 문제 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct compare {
	bool operator()(int a1, int a2) {

		int first_abs = abs(a1);
		int second_abs = abs(a2);

		if (first_abs == second_abs) // 절댓값이 같다면 음수를 기준으로
			return a1 > a2;
		else // 그게 아니라면 그냥 절댓값을 기준으로
			return first_abs > second_abs;
	}
};

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	priority_queue<int, vector<int>, compare>myQueue;

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;

		if (x == 0) {
			if (myQueue.empty()) {
				cout << '0' << '\n';
			}
			else {
				cout << myQueue.top() << '\n';
				myQueue.pop();
			}
		}

		else {
			myQueue.push(x);
		}

	}
}