[C++][BOJ 7662 이중 우선순위 큐] multiset

백준 이중 우선순위 큐

 

문제를 읽고 priority_queue 오름차순, 내림차순 2개를 사용해서 풀었으나 고려해야할 부분이 더 생겼고 결국 틀렸다.

 

priority_queue 처럼 자동으로 정렬되면서 대신 앞 뒤 두 방향으로 다  접근 가능한 container가 set이라는 것을 찾았다.

그런데 set은 중복이 허용되지 않고 중복이 허용되는 것은 multiset이었다.

 

헤더파일 : #include <set>

multiset 사용법

 multiset은 기본으로 오름차순 정렬된다.

 

[소스 코드] multiset 사용

// multiset 사용법  
#include <iostream>
#include <string>
#include <set> 
using namespace std;
typedef long long ll;

void Solve(){
	int testCase;
	cin>>testCase;
	while(testCase--){
		int k;cin>>k;
		multiset<ll> ms;
		
		for(int i = 0 ; i < k ;i++){

			char c; ll num;
			cin>>c>>num;

			switch(c){
				case 'I':{
					ms.insert(num);
					break;
				}
				case 'D':{
					if(!ms.size()) break;
					if(num==1){
						ms.erase(--ms.end());
					}
					else{
						
						ms.erase(ms.begin()); 
					}		
					break;
				}	
			}
		}
		
		if( ms.size()) cout<<  *(--ms.end() )<<" " << *ms.begin()<<"\n";
		else cout<<"EMPTY\n";
		
	}
}

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

	Solve();

}

 

 

[틀린 코드] priority_queue 2개 사용

#include <iostream>
#include <string>
#include <queue> 
using namespace std;
typedef long long ll;

enum ActionType{
	I,D,
};
void Solve(){
	int testCase;
	cin>>testCase;
	while(testCase--){
		int k;cin>>k;
		int cnt = 0;//전체 원소 개수  
		int cnt_delete = 0;//실제 D 연산 수  
		priority_queue<ll> Q1;
		priority_queue<ll,vector<ll>,greater<ll>> Q2;
		
		for(int i = 0 ; i < k ;i++){
			ActionType actionType;
			char c; ll num;
			cin>>c>>num;
			actionType = c=='I'?I:D;
			switch(actionType){
				case I:{
					Q1.push(num);
					Q2.push(num);
					cnt++;
					break;
				}
				case D:{
					if(cnt >= cnt_delete+1){
						if(num==1){
						Q1.pop();
						}
						else{
							Q2.pop();
						}
						cnt_delete++;
					}
					
					break;
				}
					
			
			}
		}
		if( Q1.size()+Q2.size()-cnt <= 0) cout<<"ENPTY\n";
		else{
			cout<< Q1.top()<<" "<<Q2.top()<<"\n";
		}
	}
}

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

	Solve();

}