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

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

7662번: 이중 우선순위 큐

문제

---

풀이

가장 큰 값과 가장 작은 값을 명령어에 따라 삭제해야 하는 문제입니다.

우선순위 큐라는 단어에 휩싸여서 처음에는 max heap 형태의 pq를 통해 top(max값) 을 구하고, 마지막 원소를 제외하고 또 다 pop을 하여 min값을 구하는 식으로 구현했는데, 그런식으로 하면 시간초과가 났습니다.

min값을 구하기 위해서 기존 원소들을 다 제거하는 방식이었으므로 logN + logN-1 + ... log1 번의 연산이 필요했습니다.

 

→ 즉 max값과 min값을 logN 정도로는 구해야 시간초과가 나지 않을 것이라 판단했습니다.

따라서 이 문제에서 말하는 것은 이중 우선순위 큐 이지만, 최대값과 최소값 둘 다를 빠르게 접근하기 위해 Multi Set을 사용하겠습니다.

(우선순위 큐는 우선순위가 가장 높은 값 하나만을 탐색하기에 적합합니다.)

 

< multiset의 특징 >

1. set이면서도 원소가 중복됨을 허용합니다.

2. BST(이진 탐색 트리)구조로 기본적으론 오름차순 정렬을 합니다.
(또한 AVL 트리 구조여서 탐색 시간은 O(logN)을 보장합니다)

즉 항상 multiset의 begin()에는 최소값이, --end() (end()가 아닌 그 앞에 마지막 원소가 존재합니다)에는 최대값이 존재하게 됩니다.

 

이를 이용하여 D 1 일 땐 multiset.erase(--multiset.end()), D -1 일 땐 multiset.erase(multiset.begin())  을 진행합니다.

---

코드

#include<iostream>
#include<set>

using namespace std;

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

	int t, k, n;
	char ins;
	cin >> t;
	while (t--) {
		multiset<int> ms;
		cin >> k;
		while (k--) {
			cin >> ins >> n;
			if (ins == 'I') {
				ms.insert(n);
			}
			else {
				if (ms.empty()) continue;

				if (n == 1) {
					ms.erase(--ms.end());
				}
				else {
					ms.erase(ms.begin());
				}
			}
		}

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

	return 0;
}