C++ 백준 11286 절댓값 힙

백준 11286

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

11286번: 절댓값 힙

풀이 전 나의 생각

 

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

이러한 조건을 만족하는 절댓값 힙에 연산 N이 주어졌을 때,
출력되는 결과를 구해야 한다.

조건

- N(1≤N≤100,000)

- 입력되는 정수는 -2^31보다 크고, 2^31보다 작다.

 

과정

가장 작은 값을 출력하고 값을 바로 제거할 수 있는 자료구조인
우선순위 큐를 사용하면 문제를 쉽게 해결할 수 있다.

하지만 아무 조건 없이 실행되는 우선선위 큐는 자료의 최댓값을 찾아주기 때문에
문제에서 요구하는 비교 연산을 직접 만들어서 넣어줘야 한다.

앞서 말했듯이 우선순위 큐는 최대를 찾아주는 자료구조기 때문에

return a > b의 형태로 최소를 찾아줘야 한다.
여기서 a > b의 의미는 기존에 있는 큐의 원소 a와 새로 들어오는 원소 b를
비교했을 때, a가 더 크다면 true가 되니 b가 우선 순위가 높아져서
내림 차순으로 정렬된다.

이어서 절댓값이 가장 작은 값을 출력하지만 절댓값이 가장 작은 값이 여러개라면
최소를 출력한다고 나와있다.

 

따라서 이 부분을 오퍼레이터로 처리해주고 우선순위 큐에 비교 연산으로
넣어주면 문제를 해결할 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	struct Compare
	{
		bool operator()(const int& a, const int& b)
		{
			//절댓값이 같다면 같은 것 중에서 최소값 반환
			if (abs(a) == abs(b))
			{
				return a > b;
			}
			//절댓값이 다르다면
			else
			{
				//절댓값 중에 작은 값 반환
				return abs(a) > abs(b); 
			}	
		}
	};
	
	priority_queue<int, vector<int>, Compare> pq;
	int N;
	cin >> N;

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

		if (x == 0)
		{		
			//큐가 비어있다면 0 출력
			if (pq.empty())
			{
				cout << "0" << '\n';
				continue;
			}
			cout << pq.top() << '\n';
			pq.pop();
		}
		else
		{
			pq.push(x);
		}
	}
}