백준 11286 절댓값 힙 [C++] 코드 및 풀이 우선순위 큐(priority_queue)

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
#include<queue>

using namespace std;

//A번 설명
struct compare
{
	bool operator()(int a1, int a2)
	{
		int first = abs(a1);
		int second = abs(a2);

		if(first == second)
		{
			return a1 > a2;
		}
		else
		{
			return first > second;
		}
	}
};

int main()
{
	int num;
	cin >> num;
	
	priority_queue<int, vector<int>, compare> q;

	//B번 설명
	for (int i = 0; i < num; i++)
	{
		int n;
		cin >> n;

		if (n == 0)
		{
			if (q.size() != 0)
			{
				int a = q.top();
				q.pop();
				cout << a << '\n';
			}
			else
			{
				cout << 0 << '\n';
			}
			
		}
		else
		{
			q.push(n);
		}
	}
	return 0;
}

풀이

문제를 해석해보겠습니다.

입력하는 자료는 다음과 같습니다.

1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0

 

1. 입력 순서대로 queue에 push합니다.

2. 입력 중 0을 만났을 경우 queue에 있는 정수 중, 절대값이 가장 작은 값을 출력합니다.

    2.1 가장 작은 절대값이 여러개인 경우, 가장 작은 수를 출력합니다.

    2.2 출력할 값이 없는 경우 0을 출력합니다.

                 (3번보면 계속 제거하기에 그리고 처음부터 0이 나올 수 있기에 값이 없을 수 있습니다.)

3. 출력한 값은 배열에서 제거합니다.

4. 1에서부터 다시 반복

 

그럼 간단하게 생각 해 보면

queue에 값들을 push하다가 0을 만났을 때 정렬된 queue에서 작은 값을 출력하면 되는 문제입니다.

(물론 2.2번과 같은 경우 0을 출력하라는 조건만 있으면 되겠죠.)

 

그럼 queue를 정렬해야하는 문제가 생깁니다.

그냥 우선순위 큐의 기능인 오름차순 그리고 내림차순 기능을 사용하면 안되나? 할 수 있지만,

-2, -1이 있는 경우 절대값이 작은 1이 먼저 오게되고 뒤따라 2가 옵니다.

하지만 단순한 오름 그리고 내림 기능을 수행하면 -2가 앞으로 오게되겠죠.

따라서 정렬 함수를 따로 만들어주면 됩니다.   

A번 설명

먼저 수를 출력하기 위하여 정렬하는 함수가 필요하게 되고, 절댓값으로 하였을 때, 같다면 원본 정수의 차이를 보면 됩니다.

일단 보겠습니다.

 

첫번째 if문 즉 절대값이 같을 때는 다음과 같습니다.

그림과 같이 처음으로 1이 Q에 push되었을 때는 아무런 일이 일어나지 않을 것 입니다.

그리고 -1이 들어오게 되면서 A번 코드가 실행될 것 입니다.

 

true일 때, 우선순위가 1은 낮아지고, -1은 높아집니다. (우선순위큐는, 우선순위가 높을 수록, 빨리 pop하는 특성을 가지고 있습니다.)

 

B번 설명

쉽게 말하자면, 

0일 때

- q에 아무요소가 없는 경우 0을 출력

- pop

 

0이 아닐때

-q에 요소를 넣고, 정렬

이렇게 수행하면 정답이 나옵니다.