백준 7662번 - 이중 우선순위 큐 (C++)

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

 

이름 처럼 우선순위큐를 반드시 두개 사용해야 풀 수 있다.

 

1 2 3 4 가 값으로 들어온다면,

 

하나의 큐는 1 2 3 4 순으로

다른 하나의 큐는 4 3 2 1 순으로 우선순위가 구성되어야 한다. 즉, 최대힙과 최소힙이 필요하다.

 

아이디어 1.

언제나 최대힙의 top > 최소힙의 top 이면 되지 않을까

 

즉, 만약 최대힙에서 pop을 3번, 최소힙에서 pop을 1번 하게 되면 최대힙의 top은 1이고 최소, 힙의 top은 2이다. 

위의 원칙을 어겼다. 이 뜻은 이미 최소힙의 top은 최대힙에서 pop되었다는 의미이기 때문이다. 하지만 이 방법은 20퍼센트에서 틀렸습니다를 받았다.

 

만약 모든 수가 다르다는 조건이 있었다면 맞았을 지 모르겠으나 만약

 

1 1 1 1 이 들어오고 2번의 최소힙 최대힙 pop이 들어오면 원래는 EMPTY가 출력되어야하지만 위의 논리대로면 이 조건을 해결할 수 없다. 한번만 pop이 되어도 최대힙의 top이 더 크지 않다고 하여 초기화되어 버릴 것이다.

 

정해: 갯수를 저장해두자.

갯수를 저장해두는 맵을 떠올리는 것이 핵심인 문제였다. 만약 1 1 1 1 이 들어왔다면 map[4] = 4 이고 큐에서 1이 pop될때마다 1의 갯수를 줄여준다.

 

그리고 pop한 후 두 개의 큐를 검사하여 만약 top이 허수라면 지워준다.

 

이 문제의 연산 개수는 1,000,000 이다. 그리고 우선순위큐의 시간복잡도는 삽입삭제 모두 log(N)을 갖는다. 

백만 * log 백만 * (top이 카운트인지 세는 연산까지) 하면... 대체 시간복잡도가 말이 되는 건가?

 

라고 생각했는데 1.5초에 통과됐다; 

 

이렇게 중간에 반복이 돌게되는 문제의 시간복잡도 계산은 너무 어려운 것 같다..

 

그리고 다른 C++ 코드들은 int로 돌아가던데 난 long 으로 돌려야 통과가 되었다. STL의 우선순위큐에 무언가 오버플로가 걸리는 것 같다.

 

* 

원인을 알았다..!! 

정수 형식의 특성

C# 형식/키워드범위

short	-32,768 ~ 32,767
ushort	0 ~ 65,535
int	-2,147,483,648 ~ 2,147,483,647
uint	0 ~ 4,294,967,295

정수형의 범위를 보면 MIN_INT 의 절댓값이 MAX_INT 보다 1 크다. 그러므로 내 방법대로 하면 -value 했을 때 정수형의 범위를 넘어버리는 것이었다!!

 

지금까지 모든 우선순위큐 문제를 이렇게 풀었는데.... 모두 값의 범위가 이렇게 크지 않았던 문제들이어서 그랬던 것이다.

 

오늘 하나 배웠다.

 

*

#include <iostream>
#include <queue>
#include <map>
#define ll long long
using namespace std;

map<ll, int> cnt;
priority_queue<ll> pq;
priority_queue<ll> rev_pq;

void MaxdeleteQueue(){
	if(!pq.empty()){
		cnt[pq.top()]--;
		pq.pop();
	}

	while(!pq.empty() && cnt[pq.top()] == 0){
		pq.pop();
	}

	while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
		rev_pq.pop();
	}
}

void MindeleteQueue(){
	if(!rev_pq.empty()){
		cnt[-rev_pq.top()]--;
		rev_pq.pop();
	}

	while(!pq.empty() && cnt[pq.top()] == 0){
		pq.pop();
	}
	while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
		rev_pq.pop();
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T; cin >> T;

	for(int t = 0; t < T; t++){
		int N; cin >> N;
		while(!pq.empty()) pq.pop();
		while(!rev_pq.empty()) rev_pq.pop();
		cnt.clear();

		for(int i = 0; i < N; i++){
			char op;
			ll value;

			cin >> op >> value;

			if(op == 'I'){
				pq.push(value);
				rev_pq.push(-value);
				cnt[value]++;
			}else if(op == 'D'){                
				if(value == 1){
					MaxdeleteQueue();
				}else{
					MindeleteQueue();
				}
			}
		}
        
        while(!pq.empty() && cnt[pq.top()] == 0){
		    pq.pop();
    	}
	    while(!rev_pq.empty() && cnt[-rev_pq.top()] == 0){
	    	rev_pq.pop();
	    }
        
		if(pq.empty() || rev_pq.empty()){
			cout << "EMPTY" << '\n';
			continue;
		}
		cout << pq.top() << ' ' << -rev_pq.top() << '\n';
	}
}