백준 7662: 이중 우선순위 큐 [C++]

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

 

시간제한 6초여서 어떻게 문제 시간제한이 6초? 했는데 6번의 시도 6번의 시간초과로 얕본 업보를 받음

문제자체는 단순하다... 수를 입력받고 명령에 따라 최댓값이나 최솟값을 삭제하기.

 

1트로는 그냥 깡 배열에 저장하고 최대냐 최소냐 입력받는 것에 따라 매번 sort를 통해 재정렬 후 삭제했다. 당연하지만 시간초과다. 쓰면서도 안 될 것 같았다

그럼 제목에도 나와있듯 우선순위 큐를 쓰긴 써야 할 것 같은데, top이 최소냐 최대냐는 최소히프냐 최대히프냐에 따라 달라지므로 우선순위 큐 두 개가 필요하다.

두개를 만들어서 저장해서 쓴다고는 치자. 문제는 두 큐를 동기화시키는 것이다. 최솟값 빼래서 최소히프에서 뺐는데 최대히프에서는 안 빼면 나중에 뭔가 잘못될 테니까.. 그럼 그걸 대체 어떻게 동기화를 시키지? 했는데,

어쨌든 이 문제의 최소/최대히프에서 중요한건 내부 상태 전체보다는 top의 원소이다.

그러니까 현재 top에 있는 것이 유효한지만 봐주면 된다는 뜻이다.

 

void syncQueue(){
    while(!max_pq.empty() && cnt[max_pq.top()]==0) max_pq.pop();
    while(!min_pq.empty() && cnt[min_pq.top()]==0) min_pq.pop();
}

cnt는 int, int 형태의 맵이다. 각 숫자의 등장 횟수를 저장한다.

즉 위와 같은 함수를 통해 pq의 top을 항상 유효한 상태로 만들어줄 수 있다.

 

그래서 이걸 써서 구현을 했더니 또또 시간초과가 떴다. 이유는 지역변수 사용 때문이었다. 처음 제출했을 땐 테스트케이스마다 pq와 map을 새로 선언했는데, 이 부분이 문제였던 것.... 전역변수 선언으로 시간 효율성을 높여주면 다행히 정답이 뜬다.

 

단순해 보였지만 실상은 그다지... 골드는 괜히 골드가 아닌갑다

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

priority_queue<int, vector<int>, greater<>> min_pq;
priority_queue<int, vector<int>, less<>> max_pq;
map<int, int>cnt;

void syncQueue(){
    while(!max_pq.empty() && cnt[max_pq.top()]==0) max_pq.pop();
    while(!min_pq.empty() && cnt[min_pq.top()]==0) min_pq.pop();
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	
    int t, k, n;
    char cmd;
    cin >> t;
    
    while(t--){
        while(!max_pq.empty()) max_pq.pop();
        while(!min_pq.empty()) min_pq.pop();
        cnt.clear();
        
        cin >> k;
        while(k--){
            cin >> cmd >> n;
            if(cmd=='I'){
                max_pq.push(n);
                min_pq.push(n);
                cnt[n]++;
            }
            else{
                if(n==1){ //최댓값삭제
                    if(!max_pq.empty()){
                        int target = max_pq.top();
                        max_pq.pop();
                        cnt[target]--;
                    }
                }
                else { //최솟값삭제
                    if(!min_pq.empty()){
                        int target = min_pq.top();
                        min_pq.pop();
                        cnt[target]--;
                    }
                }
                syncQueue();
            }
        }
        
        syncQueue();
        if(max_pq.empty() || min_pq.empty()) cout << "EMPTY" << '\n';
        else cout << max_pq.top() << ' ' << min_pq.top() << '\n';
    }
    
    return 0;
}