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

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

7662번: 이중 우선순위 큐

우선순위 덱은 왜 없는지 모르겠다...

문제를 요약하자면 삽입연산, 최솟값 삭제 연산, 최댓값 삭제 연산등 총 3가지 연산이 있는데, 이 들의 연산이 끝난 후 남아있는 최댓값과 최솟값을 구하는 문제이다.

여러모로 탈탈 털렸으나 배울 점이 많은 것 같다.

생각해야 할 점:

1.

우선 입력 받은 수가 존재하는 지, 몇개가 존재하는 지에 대해 알아야하므로 map을 이용해 삽입, 삭제 연산이 일어날 때마다 map 내의 정보들을 갱신해줘야한다.

2. 

최대 값과 최솟 값을 뽑아내기 위해 최소 힙과 최대 힙 2가지를 이용한다.

3

삭제가 일어날 때마다,  반대 힙의 숫자도 뺄수 있으면 빼야한다.

3번 이게 무슨 말이냐면, 만약 -10과 10각각 두 힙에 존재 할 때, 최소 삭제와 최대 삭제를 각각 이행 하면 원래대로라면,

최소힙에는  10이 남아있고, 최대 힙에는 -10이 남게 되는데, 여기서 삽입 연산으로 20이 한번 더 일어나면 각각 힙은 10과 20을 가리키게된다. 

이런 연산이 반복되다 보면 삭제되어야 할수와 새로 삽입된 수가 층층이 겹을 이뤄 최소, 최대 연산이 제대로 안될수 있다

4

각 테스트 케이스마다 힙들과 map을 초기화해야한다. 

 

다음은 정답 코드이다.

<정답>

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

priority_queue <int, vector<int>, greater<int> > minQ; // 최소 
priority_queue<int, vector<int>, less<int>> maxQ;
map<int, int> cnt;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;

	while (T--) {
		// 큐 비우기
		while (!maxQ.empty()) {
			maxQ.pop();
		}
		while (!minQ.empty() ) {
			minQ.pop();
		}
		cnt.clear();

		int K;
		cin >> K;



		while (K--) {
			char op;
			int data;

			cin >> op >> data; // 시작
			if ( op == 'D') {
				if (maxQ.empty() || minQ.empty()) { // 큐 내부 갯수가 없으면 
					//cout << "EMPTY" << "\n";
					//isEmpty = true;
					continue;
				}
				else if (!maxQ.empty() && data == 1) {
					//	cout << "max top: " << maxQ.top() << "\n";
					cnt[maxQ.top()]--;
					maxQ.pop();

					//	cout << "최대 큐 삭제, cnt: " << cnt << "\n";
				}

				else if (!minQ.empty()&&data == -1) { // data ==-1
					// 최소 삭제
				//	cout << "min top: " << minQ.top() << "\n";
					cnt[minQ.top()]--;
					minQ.pop();

					//	cout << "최소 큐 삭제, cnt: " << cnt << "\n";
				}
				while (!maxQ.empty() && cnt[maxQ.top()] == 0) {
					maxQ.pop();
				}
				while (!minQ.empty() && cnt[minQ.top()] == 0) {
					minQ.pop();
				}

			}// delete 연산

			else if (op == 'I') {
				maxQ.push(data);
				minQ.push(data);
				cnt[data]++;
			} // insert 연산

		} // k
		while (!maxQ.empty() && cnt[maxQ.top()] == 0) {
			maxQ.pop();
		}
		while (!minQ.empty() && cnt[minQ.top()] == 0) {
			minQ.pop();
		}

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

	}// test case


	return 0;
}