[BOJ-7662] 이중 우선순위 큐(C++)

 

백준 7662 이중 우선순위 큐

 

7662번: 이중 우선순위 큐

 

문제 설명

 

 - 이중 우선순위 큐를 구현하여, 데이터 삽입과 삭제 연산을 구현하라.

 

 - 데이터 삭제 시 우선순위가 가장 높은 것과 가장 낮은 것을 삭제할 수 있다.

 

 - Q에 적용될 연산을 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하라.

 

 - 연산 후 Q가 비어있다면, "EMPTY"를 출력하라.

 

---

 

입력 값

 

 - 테스트 데이터 T가 주어진다.

 

 - 각 테스트 데이터 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는  K가 주어진다.

   ( K <= 1,000,000 )

 

 - 이어지는 K줄 각각엔 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어진다.

 

 - 'I n'은 정수 n을 Q에 삽입하는 연산을 의미한다.

 

 - 'D 1'은 Q에서 최댓값을 삭제하는 연산을 의미한다.

 

 - 'D -1'은 Q에서 최솟값을 삭제하는 연산을 의미한다.

 

 - 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제된다.

 

 - Q가 비어있는데 적용할 연산이 'D' 라면 이 연산은 무시해도 된다.

 

 - Q에 저장될 모든 정수는 32비트 정수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 우선순위큐를 이용하는 문제이다.

 

 - C++에서 제공하는 multiset을 이용하면, 중복 값을 허용하는 heap 자료구조를 사용할 수 있다.

 

 - 여기서 주의할 점은 노드 삭제 시 값으로 삭제하게 된다면 중복 값이 모두 삭제된다는 점이다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include <cstdlib>
#include<unordered_map>
#include<unordered_set>
using namespace std;

multiset<int> ms;

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

	int tc,t;

	cin >> tc;

	for (int i = 0; i < tc; i++) {

		ms.clear();

		cin >> t;

		char oper;
		int n;

		for (int j = 0; j < t; j++) {
			cin >> oper >> n;

			if (oper == 'I') {
				ms.insert(n);
			}
			else {
				if (ms.empty()) {
					continue;
				}

				if (n == 1) {
					int val = *ms.rbegin();
					int cnt = ms.count(val);
					ms.erase(*ms.rbegin());

					if (cnt > 1) {
						for (int i = 1; i < cnt; i++) {
							ms.insert(val);

						}
					}

				}
				else {
					ms.erase(ms.begin());

				}
			}

		}

		if (ms.empty()) {
			cout << "EMPTY\n";
		}
		else {
			cout << *ms.rbegin() << " " << *ms.begin() << "\n";
		}
		
	}

	return 0;
}