[백준 11286번/c++] 절댓값 힙

알고리즘

 

자료구조, 우선순위 큐

 

---

문제 핵심

입력받은 값들을 절댓값을 기준으로 내림차순으로 뽑아야 한다.

코드는 다음과 같다.

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pQ;

greater는 오름차순 정렬로 큐의 경우 front에서 원소를 빼내므로 오름차순으로 정렬하여야 맨 앞에 가장 작은 값이 온다.

pair의 첫 번째는 입력받은 값의 절댓값으로, 두 번째는 입력받은 값으로 설정한다.

pQ.push({abs(t), t});

 

---

전체 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int main(){
	// freopen("input.txt", "rt", stdin);
	int n, t, i;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pQ;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &t);
		if(t){
			pQ.push({abs(t), t});
		} else{
			if(!pQ.empty()){
				printf("%d\n", pQ.top().second);
				pQ.pop();
			} else{
				printf("0\n");
			}
		}
	}
	
	return 0;
}