[백준] 7662 이중 우선순위 큐

✔️ 문제 링크

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

7662번: 이중 우선순위 큐

---

✔️ 문제 이해

◾ 이중 우선순위 큐를 구현하고 사용한 결과를 출력해야한다. 이중 우선순위 큐는 아래와 같이 정의된다.

1. 데이터를 삽입한다.

2. 우선순위가 가장 높은 데이터를 삭제한다.

3. 우선순위가 가장 낮은 데이터를 삭제한다.

◾ 테스트 케이스가 주어지고 명령어들이 주어진다. 명령어는 아래와 같다.

1. I 숫자 : 숫자를 우선순위 큐에 삽입한다.

2. D 1 : 우선순위 큐에서 우선순위가 가장 높은 데이터를 삭제한다.

3. D -1 : 우선순위 큐에서 우선순위가 가장 낮은 데이터를 삭제한다. 

◾ 각 테스트 케이스의 명령어들을 수행한 후 우선순위 큐에 들어있는 원소중 최대값과 최소값을 출력한다. 

◾ 우선 순위 큐가 비어있으면 "EMPTY" 를 출력한다.

---

✔️ 설계

◾ max heap과 min heap 두 개의 우선순위 큐를 활용한다.

◾ D 1 명령어를 수행하기 위해 max heap을 활용한다.

◾ D -1 명령어를 수행하기 위해 min heap을 활용한다. 

◾ map<숫자, 숫자의 개수>을 사용하여 max heap과 min heap의 데이터를 동기화 한다. ( max heap에서 삭제된 원소는 min heap에서도 삭제돼야한다. 반대도 마찬가지)

◾ map을 이용해 숫자를 조회할때 숫자의 개수가 0이면 삭제된 데이터이다. 자세한 설명은 주석으로 남겼다.

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<queue>
#include<map>
using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t; // 테스트 케이스 입력.

	while (t--) {

		int k;
		map<long long, int> m; // <숫자, 숫자의 개수> 
		priority_queue<long long> maxHeap;
		priority_queue<long long> minHeap;

		cin >> k; // 명령어 개수 입력.

		for (int i = 0; i < k; i++) { 
			char op; long long num;
			cin >> op >> num; // 명령어 입력.

			if (op == 'I') { // 이중 우선순위 큐에 숫자 삽입.
				m[num]++; // 동기화를 위해 map에 숫자 개수 기록.
				maxHeap.push(num);
				minHeap.push(-num);
			}
			else if (op == 'D') {
				if (num == 1) { 

					// 숫자의 개수가 0이란 뜻은 삭제된 데이터란 뜻으로 모두 삭제한다.
					while (!maxHeap.empty() && m[maxHeap.top()] == 0) {
						maxHeap.pop();
					}

					if (!maxHeap.empty()) { 
						m[maxHeap.top()]--;  // 개수를 빼준다.
						if (m[maxHeap.top()] < 0) m[maxHeap.top()] = 0;
						maxHeap.pop(); // 최대값 삭제.
					}
				}
				else if (num == -1) { 

					while (!minHeap.empty() && m[-minHeap.top()] == 0) {
						minHeap.pop();
					}

					if (!minHeap.empty()) {
						m[-minHeap.top()]--; // 개수를 빼준다.
						if (m[-minHeap.top()] < 0) m[-minHeap.top()] = 0;
						minHeap.pop(); // 최소값 삭제.
					}
				}
			}
		}

		// 위와 마찬가지. 숫자의 개수가 0이란 뜻은 삭제된 데이터란 뜻으로 모두 삭제한다.
		while (!maxHeap.empty() && m[maxHeap.top()] == 0) {
			maxHeap.pop();
		}

		while (!minHeap.empty() && m[-minHeap.top()] == 0) {
			minHeap.pop();
		}

		// 힙이 비어있을 경우.
		if (maxHeap.empty() || minHeap.empty()) {
			cout << "EMPTY" << endl;
		}
		else { // 비어있지 않을 경우 결과 출력.
			cout << maxHeap.top() << " " << -minHeap.top() << endl;
		}
	}

	return 0;
}

---

✔️ 문제 회고

◾ 아래와 같은 두 가지 문제로 한참 해맸다. 

◾ 결과 출력에 개행을 빼먹었다.

◾ 소스 코드를 보면 long long 자료형을 사용한다. 그 이유는 int 값의 범위가 비대칭이기 때문이다.

◾ (signed) int의 범위는 다음과 같다. -2,147,483,648 ~ 2,147,483,647

◾ 만약 -2,147,483,648 라는 숫자가 이중 우선순위 큐에 삽입 된다고 생각해보자. min heap에 삽입 되어질 것인데, 이때 min heap을 사용하기 위해 -를 붙여줬으므로 2,147,483,648 라는 숫자가 min heap에 들어간다. 이는 int 형으로 선언된 min heap일 경우 범위 초과가 발생한다. 따라서 long long 자료형을 사용해야한다.