백준 7662 - 이중 우선순위 큐

문제 설명

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 두 개의 기준을 가진 우선순위 큐를 만들어 주어진 쿼리를 처리하는 것이다.

쿼리의 종류로는 삽입, 삭제가 있다. 삭제의 경우 최댓값을 삭제하는 연산과 최솟값을 삭제하는 연산으로 나눠진다.

 

가장 간단한 방법으로는 요소를 추가하면 정렬하여 쿼리를 수행하면 된다.

하지만, 시간 초과가 발생한다.

그렇다면 삭제 연산에서 정렬해도 괜찮지 않을까라고 생각할 수 있다.

하지만, 역시 시간 초과가 발생한다.

 

시간 초과가 발생하는 이유는 많은 수를 정렬하는 빈도수가 높기 때문이다.

이 부분에서 아이디어를 얻어 자료구조를 분할하면 된다고 생각할 수 있다.

최대 힙과 최소 힙으로 나눠 수를 관리한다면 삭제 연산에 대해 효율적으로  처리할 수 있을 것이다.

이렇게 처리하면 두 가지 문제가 생긴다.

• 최대 힙과 최소 힙중 어디에 수를 삽입할지 결정해야 함
• 두 힙중 하나의 힙이 비었을 경우 다른 힙에서 마지막에 있는 요소를 지워야 함

두 문제는 하나의 방법으로 해결할 수 있다.

삽입 연산에서 두 힙에 모두 저장한 뒤, 삽입한 요소의 개수를 세면 된다.

우선, 두 힙에 모두 저장하게 되면 첫 번째 문제는 해결된다.

그럼 개수를 세는 것으로 어떻게 두 번째 문제를 해결하는지 살펴보자.

두 힙에 모두 수를 저장하게 되면 실제 데이터보다 2배로 많은 수를 저장하게 된다.

즉, 힙에 존재하는 수가 실제로 유지되는 것과는 다르게 된다는 말이다.

그렇다면 힙에 있는 수가 의미 있게 만들어 주기 위해서는 실제로 존재하지 않는 수는 지워주는 작업을 수행해야 한다.

이 작업은 유일한 수가 두 힙에 모두 저장되어 있을 때 D연산을 수행하는 상황을 살펴보면 이해할 수 있다.

123이라는 수가 I연산을 통해 삽입된 후 D 1연산을 통해 가장 큰 값을 제거한 상황을 가정해 보자.

그렇다면 위 그림과 같이 123은 최소 힙에만 남아 있게 된다.

하지만, 이는 유효하지 않은 수이다.

따라서, 올바른 값을 유지하기 위해서는 이 값을 없애줘야 한다.

이 과정에서 힙에 삽입된 수의 개수를 세어 두 힙의 top에 존재하는 수가 유효한 수인지 판단할 수 있다.

void Clean()
{
	while (!minHeap.empty() && cntMap[minHeap.top()] == 0) minHeap.pop();
	while (!maxHeap.empty() && cntMap[maxHeap.top()] == 0) maxHeap.pop();
}

 

정리하자면, 삽입 연산의 경우 두 힙에 모두 삽입하고 수의 개수를 1 증가시킨다.

삭제 연산에서는 해당하는 힙에서 top을 삭제한 뒤, 개수를 1 감소시킨 후 다른 힙에서 유효하지 않은 수를 제거한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, K;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
map<int, int> cntMap;

void Insert(int num)
{
	cntMap[num]++;

	maxHeap.push(num);
	minHeap.push(num);
}

void Clean()
{
	while (!minHeap.empty() && cntMap[minHeap.top()] == 0) minHeap.pop();
	while (!maxHeap.empty() && cntMap[maxHeap.top()] == 0) maxHeap.pop();
}

void DeleteMin()
{
	if (minHeap.empty()) return;

	cntMap[minHeap.top()]--;
	minHeap.pop();
}

void DeleteMax()
{
	if (maxHeap.empty()) return;

	cntMap[maxHeap.top()]--;
	maxHeap.pop();
}

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

	cin >> T;

	while (T--)
	{
		cin >> K;
		while (!maxHeap.empty()) maxHeap.pop();
		while (!minHeap.empty()) minHeap.pop();
		cntMap.clear();

		for (int i = 0; i < K; i++)
		{
			char oper;
			int num;

			cin >> oper >> num;

			if (oper == 'I')
			{
				Insert(num);
			}
			else
			{
				if (num == 1) DeleteMax();
				else DeleteMin();

				Clean();
			}
		}

		Clean();
		if (maxHeap.empty() && minHeap.empty())
		{
			cout << "EMPTY\n";
		}
		else
		{
			cout << maxHeap.top() << " " << minHeap.top() << "\n";
		}
	}
	
	return 0;
}

---