백준 7662 이중 우선순위 큐 (c++) : 피너클

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

7662번: 이중 우선순위 큐

우선순위 큐를 이용한 복잡한 문제다.

int test;
cin >> test;
while (test-- > 0) {
	priority_queue<long long> min_pq, max_pq;
	map<long long, int> m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> c >> ll;

기본 준비를 한다음

		if (c == 'D') {

만약 D를 입력받았다면 pop을 실행해야한다. 하지만 min_pq에서 값을 pop한다고 해도 max_pq의 값이 pop되지는 않는다.

값이 제거된걸 체크하기 위해 map을 사용한다. 32비트 정수니 visited배열로는 부족하다.

		if (ll == 1) {
			if (!max_pq.empty())
				while (m[max_pq.top()] <= 0) {
					max_pq.pop();
					if (max_pq.empty()) break;
				}

만약 ll이 1이라면 max_pq에서 pop을 실행해야한다. 하지만 그 전에 max_pq의 값들을 한번 체크할 필요가있다.

min_pq에서 pop을 했을경우 max_pq의 값도 pop해야 하니 여기서 체크하며 pop하는 것이다.

max_pq가 비어있지 않고 m[max_pq.top()]이 0보다 작다면 해당 값을 이미 pop됐다는 뜻이다. 여기서도 pop한다.

			if (max_pq.empty()) continue;
				m[max_pq.top()]--;
				max_pq.pop();
			}

그후 만약 max_pq가 비어있다면 건너뛰고 아니라면 m[max_pq.top()]--을 해준뒤 pop한다.

		else {
			if (!min_pq.empty())
				while (m[-min_pq.top()] <= 0) {
					min_pq.pop();
					if (min_pq.empty()) break;
				}
			if (min_pq.empty()) continue;
			m[-min_pq.top()]--;
			min_pq.pop();
		}
	}

이걸 min_pq에서도 똑같이 해준다.

	else{
		min_pq.push(-ll);
		max_pq.push(ll);
		if (m.count(ll) == 0) m[ll] = 1;
		else m[ll] += 1;
		}
	}

D가 아닌 I가 입력받아졌다면 각 q에 push해주고 (min_pq에는 -를 해준다.) m[ll] ++을 해준다.

if (!min_pq.empty())
	while (m[-min_pq.top()] <= 0) {
		min_pq.pop();
		if (min_pq.empty()) break;
	}
if (!max_pq.empty())
	while (m[max_pq.top()] <= 0) {
		max_pq.pop();
		if (max_pq.empty()) break;
	}

모든걸 끝낸뒤 한번더 q들을 확인하고

if (max_pq.empty() || min_pq.empty()) cout << "EMPTY" << '\n';
else cout << max_pq.top() << ' ' << -min_pq.top() << '\n';

두 q중 하나라도 비어있다면 EMPTY를 출력하고 아니면 각 q의 top을 출력한다.

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

using namespace std;

int n;
char c;
long long ll;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test;
	cin >> test;
	while (test-- > 0) {
		priority_queue<long long> min_pq, max_pq;
		map<long long, int> m;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> c >> ll;
			if (c == 'D') {
				if (ll == 1) {
					if (!max_pq.empty())
						while (m[max_pq.top()] <= 0) {
							max_pq.pop();
							if (max_pq.empty()) break;
						}
					if (max_pq.empty()) continue;
					m[max_pq.top()]--;
					max_pq.pop();
				}
				else {
					if (!min_pq.empty())
						while (m[-min_pq.top()] <= 0) {
							min_pq.pop();
							if (min_pq.empty()) break;
						}
					if (min_pq.empty()) continue;
					m[-min_pq.top()]--;
					min_pq.pop();
				}
			}
			else{
				min_pq.push(-ll);
				max_pq.push(ll);
				if (m.count(ll) == 0) m[ll] = 1;
				else m[ll] += 1;
			}
		}
		if (!min_pq.empty())
			while (m[-min_pq.top()] <= 0) {
				min_pq.pop();
				if (min_pq.empty()) break;
			}
		if (!max_pq.empty())
			while (m[max_pq.top()] <= 0) {
				max_pq.pop();
				if (max_pq.empty()) break;
			}
		if (max_pq.empty() || min_pq.empty()) cout << "EMPTY" << '\n';
		else cout << max_pq.top() << ' ' << -min_pq.top() << '\n';
	}
}

전체코드다.