[c++] 백준 11286, 절댓값 힙

백준 11286

알고리즘 분류 : priority queue (우선순위 큐)

입력받은 정수(0이 아닌)의 절댓값을 오름차순 정렬하고, 0을 입력받을 때마다 절댓값이 가장 작은 값을 출력하면 되는 문제다. (절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력한다.)

문제를 해결하기 위해서 우선순위 큐 자료구조를 이용한다. 이때 우선순위 큐는 내림차순 정렬을 기본으로 하기에, 인자를 추가하여 오름차순 정렬하도록 만드는 과정이 필요하다.

priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;

인자로 추가된, 비교 함수 compare는 pq가 first와 second를 모두 오름차순 정렬하도록 한다.

절댓값이 가장 작은 값이 여러 개일 때, 가장 작은 수를 출력한다는 조건 때문에, pq에 push하기 전, input이 음수인지 양수인지에 대한 판단이 필요하다.

input<0인 경우, first에 store, second에 0을 저장
input>0인 경우, first에 store, second에 1을 저장

출력의 과정에서는 만약 pq.top()의 second가 0이라면 -1을 곱해서 출력, pq.top()의 second가 1이라면 그대로 출력한다.

#include <iostream>
#include <queue>

using namespace std;
struct compare{
	bool operator()(pair<int,int> a,pair<int,int> b){
		if(a.first==b.first){
			return a.second>b.second;
		}
		else return a.first>b.first;
	}
};
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
//first와 second를 모두 오름차순으로 정렬하는 pq

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	
	int input,store;
	for(int i=0; i<N; i++){
		cin >> input;
		store=abs(input); //store는 input의 절댓값을 저장
		
		if(input==0){
			if(pq.empty()){
				cout << 0 << '\n';
			}
			else{
				if(pq.top().second==0){
					cout << -1*pq.top().first << '\n';
				}
				else{
					cout << pq.top().first << '\n';
				}
				pq.pop();
			}
		}
		else{
			if(input<0){
				pq.push(make_pair(store,0)); //input<0인 경우, second에 0을 저장
			}
			else if(input>0){
				pq.push(make_pair(store,1)); //input>0인 경우, second에 1을 저장
			}
		}
	}
}