[C++] 백준 7662번: 이중 우선순위 큐

문제 바로가기

⛳문제에서 요구하는 것⛳

1. 이중 우선순위 큐(Q)는 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제할 수 있다.

2. Q에 적용될 연산이 주어질 때, 이를 처리한 후 남은 데이터에서 최대와 최소를 출력하자.

 

🧨주어진 조건🧨

1. 정수 T의 범위는 주어지지 않았다.

2. K ≤ 1,000,000

3. N은 32비트 정수다. 즉, int로 커버된다.

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

5. 최댓값(최솟값)이 둘 이상일 때, 삭제 연산이 진행되면 하나만 삭제된다.

6. Q가 비어있는데 'D' 입력이 주어지면 이 연산은 무시해도 된다.

 

✨내가 처음 생각한 풀이✨

1. MinHeap을 구현하고, 값을 차례로 넣는다.

2. 최솟값을 삭제할 때는 root를 제거한다.

3. 최댓값을 삭제할 때는 Heap의 끝 부분 중 최댓값을 찾은 후 삭제한다.

4. 최댓값은 위 방법대로 출력하고, 최솟값은 root를 출력한다.

 

👓문제점 분석👓

1. Heap의 끝 부분에 최댓값이 있음이 보장되지 않는다.

  - 값을 삽입할 때, 부모와만 비교하기 때문에 그렇다.

2. 최대값이 있음이 보장된다고 해도 매번 최댓값을 찾아 삭제하는데 너무 오랜 시간이 걸린다.

 

✨내가 두 번째로 생각한 풀이✨

🔍질문 답변 게시판에서 힌트를 얻었다.

1. STL에서 제공하는 priority_queue를 이용하여 MaxQ, minQ와 DeletedMax, DeletedMin을 선언한다.

  - MaxQ, DeletedMin은 MaxHeap이며, minQ, DeletedMax는 MinHeap이다.

  - DeletedMin은 minQ에서 삭제된 값을 저장하고, DeletedMax는 MaxQ에서 삭제된 값을 저장한다.

2. 값을 삽입할 때, maxQ와 minQ에 둘 다 삽입한다.

3. 최솟값(최댓값)을 삭제할 때는 다음의 과정(4~5)을 따른다.

  4. minQ(MaxQ)와 DeletedMax(DeletedMin)이 같을 경우 각각 pop 한다.

  5. DeletedMin(DeletedMax)에 top을 삽입하고 minQ(MaxQ)에서 pop 한다.

6. 출력하기 전 위 4 과정을 반복한 후 MaxQ와 minQ의 top을 각각 출력한다.

 

👓문제점 분석👓

1. 사실 왜 문제인지 잘 모르겠다.

2. 같은 데이터를 돌려보면 옳은 코드와 결과가 다르다.

3. 왜 다른지는 모르겠다.
4. 그래서 백준 질문 답변 게시판에 질문을 올렸다.

 

🎯옳은 풀이🎯

1. priority_queue를 이용하여 minQ와 MaxQ를 선언한다.

2. 각 값에 대해 삭제여부를 알 수 있는 map <int, int> 형식의 data를 선언한다.

3. 삽입 연산을 할 때는 입력된 정수 M을 minQ와 MaxQ 모두에 삽입 후 data [M]의 값에 1을 더한다.

4. 삭제 연산을 할 때는 data[minQ(또는 MaxQ). top()]의 값이 0이 아닌 minQ(또는 MaxQ)에 대해서 pop을 반복한다.

5. data [minQ(또는 MaxQ). top()]의 값에 1을 뺀 뒤, minQ(또는 MaxQ)에 대해서 pop을 하며 삭제 연산을 마친다.

6. 결과 출력 전 위 4 과정을 반복한 후 MaxQ와 minQ의 top을 각각 출력한다.

 

🎈답안🎈

#include <iostream>
#include <queue>
#include <map>

#define EL "\n"

using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	while (N--) {
		int K;
		cin >> K;

		priority_queue<int, vector<int>, greater<int>> mQ;
		priority_queue<int, vector<int>, less<int>> MQ;
		map<int, int> data;
		while (K--) {
			char C;
			int M;
			cin >> C >> M;
			if (C == 'I') {
				mQ.push(M);
				MQ.push(M);
				data[M]++;
			}
			else if (C == 'D') {
				if (M == -1) {
					if (mQ.empty())
						goto OUT;

					while (data[mQ.top()] == 0) {
						mQ.pop();
						if (mQ.empty())
							goto OUT;
					}

					if(data.find(mQ.top()) != data.end())
						data[mQ.top()]--;
					mQ.pop();
				}
				else {
					if (MQ.empty())
						goto OUT;

					while (data[MQ.top()] == 0) {
						MQ.pop();
						if (MQ.empty())
							goto OUT;
					}

					if (data.find(MQ.top()) != data.end())
						data[MQ.top()]--;
					MQ.pop();
				}
			}
		OUT:;
		}

		while (mQ.size() && data[mQ.top()] == 0) {
			mQ.pop();
			if (mQ.empty())
				break;
		}
		
		while (MQ.size() && data[MQ.top()] == 0) {
			MQ.pop();
			if (MQ.empty())
				break;
		}

		if (MQ.empty())
			cout << "EMPTY" << EL;
		else
			cout << MQ.top() << " " << mQ.top() << EL;
	}

	return 0;
}