[백준] 11286 절댓값 힙 (C++)

 

문제 URL:

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

11286번: 절댓값 힙

 

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는,
   가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

이 문제는 위의 두 연산을 지원하는 절댓값 힙이 존재할 때 주어진 x값에 따라 

배열에 값을 추가하거나 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하면 되는 문제이다. 

 

문제를 풀기 위해 우선순위 큐 2개를 사용하였다. 

각각의 큐에 양수는 오름차순으로, 음수는 내림차순으로 저장한 뒤 x에 따라 연산을 진행해주면 된다.

---

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

int N, x;
priority_queue<int, vector<int>, greater<int>> pq1; // 양수 오름차순 저장 큐 (1 2 3 ...)
priority_queue<int> pq2; // 음수 내림차순 저장 큐 (-1 -2 -3 ...)

int main() {
	cin >> N;

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

		if (x == 0) {
			if (pq1.empty() && pq2.empty())  // 배열이 비어있는 경우
				cout << "0\n";
			else {
				if (pq1.empty()) {  // 양수 존재x 경우
					cout << pq2.top() << '\n';
					pq2.pop();
				}
				else if (pq2.empty()) {  // 음수 존재x 경우
					cout << pq1.top() << '\n';
					pq1.pop();
				}
				else {  // 양수, 음수 다 존재할 경우
					if (pq1.top() < -pq2.top()) {
						cout << pq1.top() << '\n';
						pq1.pop();
					}
					else {
						cout << pq2.top() << '\n';
						pq2.pop();
					}
				}
			}
		}
		else if (x > 0)  // 양수일 때
			pq1.push(x);
		else  // 음수일 때
			pq2.push(x);
	}
}