이중 우선순위 큐

#include <iostream>
#include <queue>

using namespace std;

long long visited[1000001];

int main(void)
{
	long long T = 0;
	cin >> T;
	for (long long i = 0; i < T; i++)
	{
		long long k = 0;
		cin >> k;
		long long count = 0;
		priority_queue<pair<long long, long long>> pq1;
		priority_queue<pair<long long, long long>> pq2;
		for (long long j = 0; j < k; j++)
		{
			char c = ' ';
			long long num = 0;
			cin >> c >> num;

			if (c == 'I')
			{
				pq1.push({ num,j });
				pq2.push({ -num,j });
				count++;
			}
			else if (c == 'D')
			{
				if (num == 1)
				{
					if (count > 0)
					{
						while (true)
						{
							long long k = pq1.top().second;
							pq1.pop();
							if (visited[k] == 0)
							{
								visited[k] = 1;
								break;
							}
						}
						count--;
					}

				}
				else if (num == -1)
				{
					if (count > 0)
					{
						while (true)
						{
							long long k = pq2.top().second;
							pq2.pop();
							if (visited[k] == 0)
							{
								visited[k] = 1;
								break;
							}
						}
						count--;
					}
				}
				if (count == 0)
				{
					while (!pq1.empty())
					{
						pq1.pop();
					}
					while (!pq2.empty())
					{
						pq2.pop();
					}
				}
			}

		}
		if (count == 0)
		{
			cout << "EMPTY" << endl;
		}
		else
		{
			long long max = 0;
			long long min = 0;
			if (count == 1)
			{
				while (true)
				{
					long long k = pq1.top().second;
					if (visited[k] == 0)
					{
						max = pq1.top().first;
						min = pq1.top().first;
						break;
					}
					else
					{
						pq1.pop();
					}
				}
			}
			else
			{
				while (true)
				{
					long long k = pq1.top().second;
					if (visited[k] == 0)
					{
						max = pq1.top().first;
						visited[k] = 1;
						break;
					}
					else
					{
						pq1.pop();
					}
				}

				while (true)
				{
					long long k = pq2.top().second;
					if (visited[k] == 0)
					{
						min = -pq2.top().first;
						break;
					}
					else
					{
						pq2.pop();
					}
				}

			}
			cout << max << " " << min << endl;
		}
		for (long long l = 0; l < 1000001; l++)
		{
			visited[l] = 0;
		}
	}
	return 0;
} //100 -100 -200  앞에서 빼고 뺴고 뒤에서 -50이 들어간 후 뺴고 뺴면? -100이 사라져있어야하는데 왜 있지?

말 그대로 우선순위 큐를 두 개 사용하는 문제이다.

Q에 저장된 각 정수 값 자체가 우선순위라는 말은-9 -8 39 0 -5 -8 이렇게 들어오면 39 0 -5 -8 -8 -9 이렇게 된다는 말이다.

동일한 정수가 삽입될 수 있다.

 

그러면 어떻게 문제에 접근해야 할까?

나는 우선순위 큐를 두 개 둬서 하나는 최댓값을 관리하게 하였고 다른 하나는 최솟값을 관리하게 하였다.

만약 -9 -8 39 0 -5 -8 이렇게 숫자가 들어오면

최댓값을 관리하는 큐는 39 0 -5 -8 -8 -9 이렇게 저장되고

최솟값을 관리하는 큐는 9 8 8 5 0 -39 부호를 반대로 저장하였다.

 

만약 최댓값을 빼면 최댓값을 관리하는 큐에서 pop을 하고 최솟값을 빼면 최솟값을 관리하는 큐에서 pop을 해주면 된다.

근데 여기서 주의할 점이 있다. 그냥 바로 pop을 하면 이미 제거되었던 요소를 또 제거하는 문제가 발생할 수도 있다.

그래서 제거를 할 때 제거했음을 체크해줘야 한다. pop을 하였는데 이미 제거되었던 요소이면 pop을 한번 더 진행한다.

이렇게 처음 제거되는 원소를 뽑을 때까지 pop을 진행하면 된다.

 

예를 들어 

최댓값 큐: 100 -100 -200

최솟값 큐: 200 100 -100(최솟값 큐는 부호를 반대로 저장함.)

이 있다고 하자.

최댓값을 두 번 pop 한다고 생각해 보자 그러면 큐는

최댓값 큐: -200

최솟값 큐: 200 100(이미 제거됨.) -100(이미 제거됨.)

이렇게 된다. 최솟값 큐에는 이미 제거되었어도 -100과 100의 요소가 그대로 남아있다.

이 상태에서 -50을 push 하면 큐는 

최댓값 큐: 50 -200

최솟값 큐: 200 100(이미 제거됨.) 50 -100(이미 제거됨.)

이렇게 된다.

여기서 만약 최솟값을 두 번 pop 하면 

-200과 -100이 pop이 된다. 이미 제거된 100이 또 나오게 된 것이다.(50과 -200이 나와야 함.)

이러한 문제점이 발생하기 때문에 이미 제거된 요소는 체크를 해주고 

뽑은 후 바로 이 원소가 이미 제거된 요소인지 확인하는 작업을 해줘야 한다.

 

이러한 원리로 문제를 해결하면 된다. (참고로 최솟값 큐는 부호를 반대로 저장했기 때문에 오버플로우가 발생할 수 있음.)

int형은 -2^31 이상 2^31 미만까지인데 부호를 반대로 하면 2^31이 나올 수 있음 int형에는 저장할 수 없음.