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

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

11286번: 절댓값 힙

풀이

가장 절댓값이 작은 수를 알아내야 하므로

양수는 작을수록 절댓값이 작으니 오름차순으로,

음수는 클수록 절댓값이 작으니 내림차순으로, 각각 따로따로 저장해야 한다.

 

가장 절댓값이 작은 수 한가지만 궁금하므로, heap 자료형을 사용하도록 한다.

이는 stl의 priority_queue를 사용하여 만들 수 있다.

 

 

1) 양수를 저장할 min heap

#include <queue> // priority_queue
#include <fuctional> // greater 함수

priority_queue<int, vector<int>, greater<int>> positive; // min heap

priority_queue는 기본적으로 max heap 형태라, min heap으로 사용하려면

뒤에 greater<int> 함수를 붙여 사용해야 한다.

 

 

2) 음수를 저장할 max heap

priority_queue<int> negative; // max heap 생성 방식 1
priority_queue<int, vector<int>, less<int>> negative; // max heap 생성 방식 2

max heap은 less<int> 함수를 붙여서 만들 수도 있다.

 

🌟 코드 구현

입력한 숫자가

1) 양수일 때 : positive priority_queue에 저장

2) 음수일 때 : negative priority_queue에 저장

3) 0일 때 : 양수의 top과 음수의 top을 비교하여 판단함

 

Code

#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int N;

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

	priority_queue<int, vector<int>, greater<int>> positive; // 최소 힙
	priority_queue<int> negative; // 최대 힙
	cin >> N;

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

		// 1) 양수일 때
		if (num > 0)  positive.push(num);

		// 2) 음수일 때
		else if (num < 0)  negative.push(num);

		// 3) 0일 때
		else { 
			if (negative.size()) { // 음수가 있을 때
				if (positive.size() && (positive.top() < -negative.top())) { // 양수가 존재하고, 양수의 절댓값이 더 작다면 -> 양수쪽 print/pop
					cout << positive.top() << '\n';
					positive.pop();
				}
				else { // 양수가 존재하지 않거나, 음수의 절댓값이 더 작거나 같다면 -> 음수 print/pop
					cout << negative.top() << '\n';
					negative.pop();
				}
			}
			else { // 음수가 존재하지 않을 때
				if (positive.size()) { // 양수가 존재한다면 -> 양수 print/pop
					cout << positive.top() << '\n';
					positive.pop();
				}
				else cout << 0 << '\n'; // 아무것도 존재하지 않는다면 -> 0 print
			}
		}
	}
	return 0;
}