[3주차] 백준 11286번: 절댓값 힙_C++

백준 11286: 절댓값 힙

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

11286번: 절댓값 힙

---

-> N을 입력받는다.

-> N개만큼 입력받는다.

-> 0이 아닌 정수를 입력했을 경우에는 따로 출력없이 그냥 배열에 값을 넣어준다.

-> 0을 입력했다면 배열에서 절댓값이 가장 작은 수를 출력해주고,그 값을 제거해준다.

// 단, 작은 값이 여러 개일 경우에는 가장 작은 수를 제거해준다. (즉, 음수를 제거하라는 뜻)

// 단, 배열에 값이 없을 경우는 0을 출력해준다

---

11279번은 자연수로 내림차순의 방식이었다면,

이번 문제는 정수로 오름차순의 방식이며, 절댓값으로 처리해주어야 한다. 

즉 새롭게 비교연산자를 구조체를 통해 생성해야 한다. 

 

오름차순 참고 사이트: https://travelbeeee.tistory.com/126

절댓값 abs함수 참고 사이트: https://blockdmask.tistory.com/335

---

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

struct cmp {
	bool operator()(int a, int b) {
		if (abs(a) > abs(b)) {
			return true;
		}
		else if (abs(a) == abs(b)) {
			if (a > b) {
				return true;
			}
			else {
				return false;
			}
		}
		return false;
	}
};

int main() {
	int N;
	priority_queue <int,vector<int>,cmp> pq;

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N;

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

		if (x == 0) {
			if (pq.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(x);
		}

	}
	return 0;
}

-> 우선순위 큐에 들어갈 연산자를 절대값 기준 오름차순으로 정렬하였고, 절대값이 같은 경우 더 작은 수에 우선순위를 주었다.

---

연산자 부분이 조금 헷갈려서 구글링을 통해서 해결했는데

새삼 세상에는 똑순이들이 많다.............. 부럽다