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

문제링크: https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

우선순위 큐를 사용하여서 해결하는 문제

 

접근방식

 

1.  절댓값에 대한 순서를 우선순위 큐를 활용하여 해결하자!

 

문제풀이 

 

1.  pair형태의 우선순위 큐 생성

 

2. min-heap형태로 구성!

근데, "절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력" 하라는 조건이 있으니 두번째 원소값을 변형 하여서 구현하기

 

 

 

정답코드

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

priority_queue <pair<int, int>> que;
int n = 0;
int num = 0;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--) {
		cin >> num;
		if (num == 0) {
			if (que.size() == 0)
				cout << 0 << "\n";
			else {
				cout <<  que.top().first * que.top().second  << "\n";
				que.pop();
			}
		}
		else {
			if(num > 0)
				que.push(make_pair(-1 * abs(num),-1));
			else
				que.push(make_pair(-1 * abs(num), 1));
		}

	}

	return 0;
}