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

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

 

 

알고리즘 종류

자료구조

우선순위 큐

 

 

 

사고 과정

1. 최솟값과 최댓값을 저장할 우선순위 큐 2개가 필요합니다.

 

2. 최댓값을 저장한 우선순위 큐에서 최댓값을 제거하면, isVisited 배열에 해당 숫자를 제거했다고 표시합니다. 이렇게 표시하여 최솟값 우선순위 큐에서 해당 숫자를 처리할 수 있습니다.

 

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
int tc, n;
 
int isVisited[1000001]; // 큐에 있는 숮자인지 확인하는 배열  
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> tc;
    
    while(tc--){
        priority_queue<pair<ll, ll> > maxPQ; // 숫자, 번호  
        priority_queue<pair<ll, ll> > minPQ;
        memset(isVisited, 0, sizeof(isVisited));
        
        cin >> n;
        
        char c;
        ll x;
        for(int i=0; i<n; i++){
            cin >> c >> x;
            
            if(c == 'I'){
                maxPQ.push({x, i});
                minPQ.push({-x, i});
                isVisited[i] = 1;
            }
            else if(c == 'D' && x == 1){
                while(!maxPQ.empty()){ 
                    if(isVisited[maxPQ.top().second]) break;
                    maxPQ.pop();
                }
                if(!maxPQ.empty()){
                    isVisited[maxPQ.top().second] = 0;
                    maxPQ.pop();
                }
                
            }
            else if(c == 'D' && x == -1){
                while(!minPQ.empty()){
                    if(isVisited[minPQ.top().second]) break;
                    minPQ.pop();
                }
                if(!minPQ.empty()){
                    isVisited[minPQ.top().second] = 0;
                    minPQ.pop();
                }
                
            }
        }
        
        while(!maxPQ.empty()){
            if(isVisited[maxPQ.top().second]) break;
            maxPQ.pop();
        }
        
        while(!minPQ.empty()){
            if(isVisited[minPQ.top().second]) break;
            minPQ.pop();    
        }
        
        if(maxPQ.empty() || minPQ.empty()) cout << "EMPTY" << "\n";
        else cout << maxPQ.top().first << " " << -minPQ.top().first << "\n";
    }
}

 

 

 

시행착오