[힙] 이중우선순위큐

문제설명

1. 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

2. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현하라.

• operations : 이중 우선순위 큐가 할 연산

문제해결방법

코드

[2021.03.04]

- priority_queue 사용

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<string> operations) {
    int cnt = 0, num;
    priority_queue<int, vector<int>> decre;
    priority_queue<int, vector<int>, std::greater<int> > incre;
    
    for(int i = 0; i < operations.size(); i++) {
        num = stoi(operations[i].substr(2));
        
        switch(operations[i][0]) {
            case 'I':
                decre.push(num);
                incre.push(num);
                break;
            case 'D':
                bool size = (decre.size() - cnt) > 0;
                if(num == 1 && size) {
                    decre.pop();
                }
                else if(num == -1 && size) {
                    incre.pop();
                    cnt++;
                }
                break;
        }
    }
    if(decre.size() - cnt == 0) return {0, 0};
    return {decre.top(), incre.top()};
}

---

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<string> operations) {
    int cnt = 0, num;
    priority_queue<int, vector<int>> decre;
    priority_queue<int, vector<int>, std::greater<int> > incre;
    
    for(int i = 0; i < operations.size(); i++) {
        num = stoi(operations[i].substr(2));
        switch(operations[i][0]) {
            case 'I':
                decre.push(num);
                incre.push(num);
                break;
            case 'D':
                bool size = (decre.size() - cnt) > 0;
                if(num == 1 && size) {
                    decre.pop();
                }
                else if(num == -1 && size) {
                    incre.pop();
                    cnt++;
                }
                break;
        }
        if(decre.size() - cnt == 0) {
            priority_queue<int, vector<int>> tmp1;
            priority_queue<int, vector<int>, greater<int>> tmp2;
            decre.swap(tmp1);
            incre.swap(tmp2);
            cnt = 0;
        }
    }
    if(decre.size() - cnt == 0) return {0, 0};
    return {decre.top(), incre.top()};
}

---

[2021.03.05]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    int cnt = 0, num;
    bool sorted = false;
    vector<int> nums;
    
    for(int i=0; i<operations.size(); i++) {
        num = stoi(operations[i].substr(2));

        if(operations[i][0] == 'D' && !nums.empty()) {
            if(sorted) sort(nums.begin(), nums.end());
            
            if(num == 1) {
                nums.pop_back();
            } else {  
                nums.erase(nums.begin());
            }
            sorted = false;
        }
        else if(operations[i][0] == 'I') {
            nums.push_back(num);
            sorted = true;
        }
    }
    if(nums.empty()) return {0, 0};
    return {nums.back(), nums.front()};
}