백준 11286번: 절댓값 힙

 

 

 

 

우선순위 큐를 하나는 양수, 하나는 음수로 두개를 선언하면 쉽게 해결되는 문제였다.

문제의 핵심은

1. 절댓값이 같은게 여러개라면 더 작은 수(음수)를 출력, 삭제한다.
2. 둘 중 하나의 배열이 비어있다면 비어있지 않은 배열을 출력, 삭제한다.
3. 배열 두개가 모두 비어있다면 0을 출력한다.

 

 

 

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


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int n;
	cin >> n;
	priority_queue<int,vector<int>, greater<int>> pq1;	//양수 
	priority_queue<int, vector<int>, less<int>> pq2;	//음수
	for (int i = 0; i < n; i++) {
		int op; 
		cin >> op;

		if (op > 0) {
			pq1.push(op);
		}
		else if (op < 0) {
			pq2.push(op);
		}
		else {
			if (pq1.empty() || pq2.empty()) {
				if (!pq1.empty()) {
					cout << pq1.top() << "\n";
					pq1.pop();
				}
				else if (!pq2.empty()) {
					cout << pq2.top() << "\n";
					pq2.pop();
				}	
				else 
					cout << "0\n";
			}
			else {
				if (pq1.top() < abs(pq2.top())) {
					cout << pq1.top() << "\n";
					pq1.pop();
				}
				else {
					cout << pq2.top() << "\n";
					pq2.pop();
				}
			}
			
		}
	}

	return 0;
}