[Heap] 이중우선순위 큐

<문제>

 

<문제 풀이>

(생각의 흐름)

1. 아.. 최소힙 , 최대힙이 필요하겠다. (풀 때 MultiSet의 존재 몰랐음.) "D 1"이면 최대 힙에서 pop, "D -1"이면 최소 힙에서 pop 하면 되지 않을까 라는 생각이 들었다.
2. 따라서 I명령어로 제시되는 수들을 2개의 힙에 동시에 집어넣고, 삽입되는 값들은 2개의 배열을 이용하여 값의 개수를 카운트. 2개의 배열은 "양의 정수를 세는 배열 - positive[] , 음의 정수를 세는 배열 - negative[]" 을 만든다. 수가 삽입될 때 각 수를 세는 배열에서 해당 값이 배열의 인덱스가 되어 (ex. positive[value]++) 값을 1 증가시킨다.
3. 그리고 D명령어를 수행할 때 해당 힙에서 pop을 진행하고, 배열에서 해당 value의 값을 감소 시킨다. (ex. positivie[value]--).
4. 위 과정이 명령어 끝까지 이뤄지면 2개의 배열을 통해 아직 heap안에 남아있는 값을 알 수 있다.(pop되지 않은 값들은 감소되지 않기 때문에.) 배열 내에 값이 1이상인 것들만 골라서 max와 min 값을 계산한다.
5. max , min값은 배열이 음수 배열과 양수 배열이 있기 때문에 음수에서의 max, min 과 양수일때의 max, min을 따로 구해서 후에 조건문을 통해 통합 max, min을 구해서 정답을 구한다.

디테일 : 최소힙이나 최대힙이 empty라는 것은, 한 쪽 힙도 empty 된다. 무슨 말이냐면 D 1명령어만 나와서 최대 힙이 빈 상태가 되면 나머지 heap도 비어있는 상태가 되어야 하기 때문에 한쪽 힙이 empty되는 경우에는 반드시 모든 힙을 비어주어야 한다. 

 

위 방식으로 푼

<코드 구현>

#include <string>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <iostream>

using namespace std;

int positive[1000001];
int negative[1000001];

void remove(int value) {
    if(value < 0) {
        negative[abs(value)]--;
    } else {
        // cout << "value : " << value << endl;
        // cout << "positive[value] : "  << positive[value] << endl;
        positive[value]--;
    }
}

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> pq_q;
    priority_queue<int, vector<int>, less<int>> pq_l;
    
    int p_max = -1, p_min = 1000001;
    int n_max = -1000001, n_min = 0;
    
    int value;
    int command;
    
    for(string elem : operations) {
        if(pq_q.empty() || pq_l.empty()) {
            pq_q = priority_queue<int, vector<int>, greater<int>>();
            pq_l = priority_queue<int, vector<int>, less<int>>();
        }
        switch(elem[0]) {
            case 'I':
                value = stoi(elem.substr(2));
                pq_q.push(value);
                pq_l.push(value);
                if(value < 0) {
                    negative[abs(value)]++;
                    // n_max = n_max > value ? n_max : value;
                    // n_min = n_min > value ? value : n_min;
                } else {
                    positive[value]++;
                    // p_max = p_max > value ? p_max : value;
                    // p_min = p_min > value ? value : p_min;
                }
                break;
            case 'D':
                command = stoi(elem.substr(2));
                if(command < 0) {
                    if(pq_q.empty()) break;
                    value = pq_q.top();
                    remove(value);
                    pq_q.pop();
                } else {
                    if(pq_l.empty()) break;
                    value = pq_l.top();
                    remove(value);
                    pq_l.pop();
                }
                break;
        }   
    }
    
    while(!pq_q.empty()) {
        value = pq_q.top();
        if(value < 0) {
            if(negative[abs(value)] > 0) {
               n_max = n_max > value ? n_max : value;
               n_min = n_min > value ? value : n_min;
            }  
        } else {
            if(positive[value] > 0) {
                p_max = p_max > value ? p_max : value;
                p_min = p_min > value ? value : p_min;
            }
        }
        pq_q.pop();
    }
    
    if(p_max > -1 && n_min < 0) {
        answer.push_back(p_max);
        answer.push_back(n_min);
    } else if(p_max > -1 && n_min == 0) { 
        answer.push_back(p_max);
        answer.push_back(p_min);
    } else if(p_max == -1 && n_min < 0) {
        answer.push_back(n_max);
        answer.push_back(n_min);
    } else {
        answer.push_back(0);
        answer.push_back(0);
    }
    
    return answer;
}

 

 

<훨씬 더 좋은 코딩>

-multiset을 활용한 코드 <multiset>에 대한 자료구조 정리아래.

https://ranseo.tistory.com/73

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> arguments) {
    vector<int> answer;
    multiset<int> que;
    multiset<int>::iterator iter;
    string sub;

    for(auto s : arguments) {
        sub =s.substr(0, 2);
        if(sub=="I ") que.insert(stoi(s.substr(2,s.length()-2))); 
        else if(s.substr(2,1)=="1"&&que.size()>0) { que.erase(--que.end()); }
        else if(que.size()>0) { que.erase(que.begin()); }
    }

    if(que.size()==0) { answer.push_back(0); answer.push_back(0); }
    else { 
        iter = --que.end(); answer.push_back(*iter); 
        iter = que.begin(); answer.push_back(*iter);
    }

    return answer;
}

출처: <https://programmers.co.kr/learn/courses/30/lessons/42628/solution_groups?language=cpp>