[BOJ 7662, 어려움] 이중 우선순위 큐 (C++)

개인적인 난이도

어려움

 

생각대로 안돼서 개고생함

이게 왜 골드 4인지 모르겠다

---

알다시피 priority_queue는 heap으로 구현되어 있고 출력이 최상위 루트를 통해 이루어짐
heapify() 1번의 시간복잡도는 log(N). 입출력시 heapify가 이루어짐

이 문제의 제목을 통해 우선순위 큐 2개를 이용해 푸는 것이라고 짐작할 수 있음
최댓값, 최솟값을 출력해야 하므로, max heap 1개와 min heap 1개를 쓰면 된다고 짐작할 수 있음

그렇다면 입력은 2개의 힙 모두에 이루어질 것이고 출력은 둘 중 하나의 힙에서만 이루어질 것이다~

그렇다면 두 힙의 동기화가 이 문제의 관건일 것이다~ 라고 짐작할 수 있음

 

실패한 풀이)

 

1. insert연산 수행 횟수와 delete연산 수행 횟수가 같아질 때, 모든 heap을 empty 상태로 만들기
   -> 실패
2. 두 heap 중 하나가 empty가 될 때, 둘 다 empty로 만들면서 동기화
   -> 실패
3. 두 heap중 하나의 size가 1이 될 때, 두개의 상태를 동일하게 만들면서 동기화
   -> 실패

 

안되는 이유

위처럼 코드를 짜 보면 반례가 매우 많다

한쪽 힙에 넣고 빼고 넣고 빼고 반대쪽에서도 한두번 넣고  빼고 하다 보면

양쪽 힙의 최솟값과 최댓값이 금새 달라짐

 

실패 코드

// 실패한 코드
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;
int main(void) {
	fastio;
	int T;cin>>T;
	while (T--)
	{
		priority_queue<int,vector<int>> pql;
		priority_queue<int,vector<int>,greater<int>> pqg;
		int k;cin>>k;
		int qsize=0;
		while (k--)
		{
			char op;int opr;
			cin>>op>>opr;	
			if(op=='I'){
				qsize++;
				//cout<<"insert "<<opr<<" qsize "<<qsize<<"\n";
				pql.push(opr);pqg.push(opr);
			}
			else if(op=='D'){
				if(qsize){
					if(opr==1){//pql top
						qsize--;
						//cout<<"pop1 "<<pql.top()<<" qsize "<<qsize<<"\n";
						pql.pop();
					}
					else if(opr==-1){//pqg top
						qsize--;
						//cout<<"pop2 "<<pqg.top()<<" qsize "<<qsize<<"\n";
						pqg.pop();
					}
				}
				if(!qsize){
					//cout<<"clear queue\n";
					while (!pql.empty())
					{
						pql.pop();
					}
					while (!pqg.empty())
					{
						pqg.pop();
					}
				}
			}
		}
		if(qsize){
			cout<<pql.top()<<" "<<pqg.top()<<"\n";
		}
		else cout<<"EMPTY\n";
	}
	return 0;
}

 

 

---

성공한 풀이)

map을 사용해 어떤 원소의 개수를 체크하면 된다.

한쪽 힙에서 원소를 pop할때, 그 원소가 map에 존재하며, 그 개수가 1개이상이다 --> 그것이 최댓값 or 최솟값이다.
한쪽 힙에서 원소를 pop할때, 그 원소가 map에 존재하지 않거나, 그 개수가 0개이하이다 --> 무시하고 한번더 pop

 

되는 이유

집합과 맵은 충분히 빠르다. 그중에서도, 이 문제에서는 중복된 원소가 입력될 수 있으므로 map을 이용해 원소의 개수를 세 주어야 한다

아니면 multiset 써도 될듯함

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;
int main(void) {
	fastio;
	int T;cin>>T;
	while (T--)
	{
		priority_queue<int,vector<int>> pql;
		priority_queue<int,vector<int>,greater<int>> pqg;
		map<int,int> mmp;
		int k;cin>>k;
		int qsize=0;
		while (k--)
		{
			char op;int opr;
			cin>>op>>opr;	
			if(op=='I'){
				qsize++;
				mmp[opr]++;
				pql.push(opr);pqg.push(opr);
			}
			else if(op=='D'){
				if(qsize){
					if(opr==1){//pql top
						qsize--;
						while (mmp[pql.top()]<1)
						{
							pql.pop();
						}
						mmp[pql.top()]--;
						pql.pop();
					}
					else if(opr==-1){//pqg top
						qsize--;
						while (mmp[pqg.top()]<1)
						{
							pqg.pop();
						}
						mmp[pqg.top()]--;
						pqg.pop();
					}
				}
				
			}
		}
		if(qsize){
			while (mmp[pql.top()]<1)
			{
				pql.pop();
			}
			while (mmp[pqg.top()]<1)
			{
				pqg.pop();
			}
			cout<<pql.top()<<" "<<pqg.top()<<"\n";
		}
		else cout<<"EMPTY\n";
	}
	return 0;
}

문제 난이도가 올라갈수록 set과 map의 사용 빈도가 잦아지는 것 같다