[백준] 7662번. 이중 우선순위 큐 (C++)

문제

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

 

풀이

[priority queue]

INSERT

최대힙, 최소힙에 둘 다 숫자를 넣는다

desc.push(n);
asc.push(n);

number에 해당 수가 몇개 있는지 저장한다

number[n]++;

 

DELETE

숫자를 저장하는 곳이 2개(desc,asc)라서 확인해야 하는 과정이 있다.

 

확인하려는 최소값(asc.top()) 혹은 최대값(desc.top())이 존재하는 값인지 확인해야 한다.

만약 number에서 확인한 값이 0이면 number[desc.top()] == 0  

이미 삭제된 값이라 존재하지 않는다는 의미이다. 

그렇기에 해당 값을 최소힙 혹은 최대힙에서 pop(asc.pop();, desc.pop())한다.

while (!asc.empty() && number[asc.top()] == 0)
    asc.pop();

최소 혹은 최대값을 삭제

number[asc.top()]--;
asc.pop();

 

 

코드

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

int main()
{
	//FAST INPUT,OUTPUT
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T; cin >> T;
	for (int i = 0; i < T; i++)
	{
		//INPUT
		map<long, int>number;
		priority_queue<long, vector<long>>desc;
		priority_queue<long, vector<long>,greater<long>>asc;
		int K; cin >> K;

		//CHECK
		for (int k = 0; k < K; k++)
		{
			char cmd; cin >> cmd;
			long n;

			//DELETE
			if (cmd == 'D')
			{
				cin >> n;
				if (desc.empty() || asc.empty()) continue;

				// 최대값 삭제
				if (n == 1) {
					while (!desc.empty() && number[desc.top()] == 0)
						desc.pop();
					if (!desc.empty()) {
						number[desc.top()]--;
						desc.pop();
					}
				}
				// 최소값 삭제
				else if (n == -1) {
					while (!asc.empty() && number[asc.top()] == 0)
						asc.pop();
					if (!asc.empty()) {
						number[asc.top()]--;
						asc.pop();
					}
				}
			}
			//INSERT
			else if (cmd == 'I')
			{
				//n을 삽입
				cin >> n;
				desc.push(n);
				asc.push(n);
				number[n]++;
			}
		}

		while (!desc.empty() && number[desc.top()] == 0)
			desc.pop();
		while (!asc.empty() && number[asc.top()] == 0)
			asc.pop();

		if (desc.empty() || asc.empty()) { cout << "EMPTY\n"; }
		else { cout<< desc.top() << " " << asc.top() << "\n"; }
	}
}