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

절댓값이 가장 작은 값을 제거하는 문제이다.

만약 x가 0이 아니라면 배열에 x를 추가하고 0이라면 절댓값이 가장 작은 값을 출력하면 된다.

 

어떻게 절댓값이 가장 작은 값을 출력할 수 있을까??

정렬을 하면 어떻게 될까?? -8 -3 -2 -1 1 2 3 4 5 6 7 이렇게 정렬이 되어있다면?

-1과 1은 절댓값이 같으니 같은 우선순위이고 2와 3도 동일하다. 근데 값을 넣을 때마다 정렬을 해버리면??

시간 초과.

이러한 문제점 때문에 나는 우선순위 큐를 사용하였다.

음수와 양수를 합쳐놓으면 원하는 대로 절댓값이 가장 작은 값을 제거하는 것은 불가능하기 때문에

양수 pq와 음수 pq로 나누었다.

 

이렇게 양수와 음수를 나누고 top의 값을 확인해서 더 절댓값이 작은 값을 출력하면 된다.

양수와 음수를 나누었기 때문에 우선순위 큐가 비어있는지 꼭 확인을 해줘야 한다.

비어있는 상태에서 top이나 pop을 호출하면 안 되기 때문!

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int>ppq;
priority_queue<int>mpq;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int num = 0;
		cin >> num;
		if (num != 0)
		{
			if (num < 0)
			{
				mpq.push(num);
			}
			else
			{
				ppq.push(-num);
			}
		}
		else
		{
			if (!ppq.empty() || !mpq.empty())
			{
				if (ppq.empty())
				{
					cout << mpq.top() << '\n';
					mpq.pop();
				}
				else if (mpq.empty())
				{
					cout << -ppq.top() << '\n';
					ppq.pop();
				}
				else
				{
					if (ppq.top() > mpq.top())
					{
						cout << -ppq.top() << '\n';
						ppq.pop();
					}
					else
					{
						cout << mpq.top() << '\n';
						mpq.pop();
					}
				}
			}
			else
			{
				cout << 0 << '\n';
			}

		}
	}
	return 0;
}