7662번: 이중 우선순위 큐

문제링크

C++

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int T, k;

int check[1000001];



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

    cin >> T;

    for (int i = 0; i < T; i++){
        memset(check, 0, sizeof(check));
        priority_queue<pair<int, int> > maxval;
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > minval;

        int n;
        cin >> n;
        for (int i = 0; i < n; i++){
            char chartmp;
            int inttmp;
            cin >> chartmp >> inttmp;
            if (chartmp ==     'I'){
                minval.push({inttmp, i});
                maxval.push({inttmp, i});
                check[i] = 1;
            }
            else if (chartmp == 'D'){
                if (inttmp == 1){

                    if (!maxval.empty()){
                        check[maxval.top().second] = 0;
                        maxval.pop();

                    }
                    while (!maxval.empty() && check[maxval.top().second] == 0){
                        maxval.pop();
                    }
                    while (!minval.empty() && check[minval.top().second] == 0){
                        minval.pop();
                    }
                }
                else if (inttmp == -1){
                    if (!minval.empty()){
                        check[minval.top().second] = 0;
                        minval.pop();
                    }

                    while (!maxval.empty() && check[maxval.top().second] == 0){
                        maxval.pop();
                    }
                    while (!minval.empty() && check[minval.top().second] == 0){
                        minval.pop();
                    }


                }
            }
        }
        if (!minval.empty() && !maxval.empty()){
            cout << maxval.top().first << " " << minval.top().first << "\n";

        }else{
            cout << "EMPTY\n";
        }
    }
}

• min값과 max값에 대한 우선순위 큐를 각각 만들어줬다.
• 그 후 min이나 max를 pop할 때는 각각의 우선순위 큐에서 pop해줬다.
• 하지만 min, max 우선순위 큐에 둘 다 들어있는 경우가 있기 때문에 한 쪽에서 pop한 것이 다른 쪽에 계속 남아있으면 안 된다.
• 첫번째 시도에서는 unordered_map<int, int>를 통해 키값에 들어온 정수값을, 밸류값에 해당 정수의 갯수를 담아줬습니다..만 시간초과 발생.
• 두번째 시도는 총 인스트럭션의 갯수가 1M 이하라는 점에 착안했다.
  • 따라서 각 인스트럭션의 순번을 인덱스로 하는 배열(checkp[)을 선언해도 메모리는 충분
  • 우선순위 큐는 pair로 선언해서 first에는 입력받은 정수값, second에는 인스트럭션의 순번을 넣어준다.
  • 각 인스트럭션에 들어온 정수값이 큐에 남아있으면 배열엔 true로 기록. 큐에서 없으면 false로 기록.
  • max나 pop하고 나면 그 다음 큐값은 이미 min에서 pop해서 없는 값일 수 있다. 이 때 check[]를 확인해서 없는 값이면 max에서도 계속 pop해서 제거해준다. min값을 pop할 때도 마찬가지로 확인 필요.
  • max를 pop하고 나서 보통은 maxval에 있는 값만 이미 pop된 것이 남아있는지 확인하면 된다. 하지만 큐에 원소 한 개만 남아있는 경우 max에서 pop하면 min.top()도 바로 제거해주지 않으면 min값을 pop할 때 있는 것처럼 인식하므로 minval에 있는 값들도 확인해줘야 한다. 혹시라도 이렇게 하지 않으려면 max나 min을 pop할 때 대신 체크해줘도 될 것 같다.
• 우선순위 큐의 push, pop은 모두 $O(logN)$($N$은 큐의 크기)의 시간복잡도.
  • 총 시간복잡도는 연산의 갯수 $k$에 대해 $O(k \cdot log k)$