[BOJ] 7662 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

heap(priority_queue)

 

---------------------------------------------------풀이----------------------------------------------------

 

min heap과 max heap을 동시에 사용한다.

bool Q[]를 정의해 각 인덱스의 값이 유효한지를 저장한다.

예를 들어, min heap에서는 지워졌다고 해도, max heap에선 지워지지 않은 경우를 피하기 위해서이다.

1000ms에 통과할 수 있었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

struct cmp1{
    bool operator()(pair<int,int> a, pair<int,int> b){
        return a.first > b.first;
    }
};
struct cmp2{
    bool operator()(pair<int,int> a, pair<int,int> b){
        return a.first < b.first;
    }
};

// 유효한 값인지
bool Q[1'000'001];
// 우선순위 값, Q에서의 인덱스
priority_queue<pair<int,int>, vector<pair<int,int> >, cmp1> min_heap;
priority_queue<pair<int,int>, vector<pair<int,int> >, cmp2> max_heap;
int Q_idx = 0;

void init_all(){
    while(!min_heap.empty()){
        min_heap.pop();
    }
    while(!max_heap.empty()){
        max_heap.pop();
    }
    Q_idx = 0;
}

int main(void){
    FASTIO;
    int T;
    cin >> T;
    for(int test_case = 1; test_case <= T; test_case++){
        init_all();
        int K;
        cin >> K;
        char op;
        int n;
        for(int i = 0; i < K; i++){
            cin >> op >> n;
            switch(op){
                case 'D':
                    // Q에서 최댓값 삭제
                    if(n > 0){
                        pair<int,int> cur;
                        while(!max_heap.empty()){
                            cur = max_heap.top();
                            max_heap.pop();
                            if(Q[cur.second]){
                                // 유효하지 않은 값으로 만들고 종료
                                Q[cur.second] = false;
                                break;
                            }
                        }
                    }
                    // Q에서 최솟값 삭제
                    else{
                        pair<int,int> cur;
                        while(!min_heap.empty()){
                            cur = min_heap.top();
                            min_heap.pop();
                            if(Q[cur.second]){
                                // 유효하지 않은 값으로 만들고 종료
                                Q[cur.second] = false;
                                break;
                            }
                        }
                    }
                break;
                // n을 Q에 삽입
                case 'I':
                    max_heap.push(make_pair(n, Q_idx));
                    min_heap.push(make_pair(n, Q_idx));
                    Q[Q_idx++] = true;
                break;
            }
        }
        while(!max_heap.empty() && !Q[max_heap.top().second]){
            max_heap.pop();
        }
        while(!min_heap.empty() && !Q[min_heap.top().second]){
            min_heap.pop();
        }

        if(max_heap.empty() || min_heap.empty()){
            cout << "EMPTY\n";
        }
        else{
            cout << max_heap.top().first << " " << min_heap.top().first << "\n";
        }
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

deque, list 등 이것저것 사용해보고, array에서 upper_bound를 사용해 정렬하면서 저장하는 방식도 사용해봤으며,

heap 하나로 최대를 빠르게 찾고 모두 pop하면서 최소를 찾는 방식으로도 사용해봤으나,

전부 1%이하에서 시간초과가 발생했다.

 

그리고 min heap과 max heap을 사용하는 방식으로 바꿨을 때, segmentation fault가 발생했다.

결국 찾은 문제는 test case가 여러 개인데 각 변수 초기화를 제대로 안 해준 것이다. 그래서 init_all()함수를 만들어 초기화하자 정답으로 인정되었다.(1000ms)

**초기화 함수를 만들어 초기화하는 버릇을 들이자!