[프로그래머스 C++] 이중우선순위큐

 

[프로그래머스 C++] 이중우선순위큐

 

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

---

 

 

 

해결전략

 

덱 deque

우선순위큐 priority_queue

 

---

 

 

정답코드 - deque 사용

 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
 
vector<int> solution(vector<string> oper) {
    vector<int> answer;
 
    deque<int> dQ;
 
    for (int i = 0; i < oper.size(); i++)
    {
        if (oper[i][0] == 'I') {
            int num = stoi(oper[i].substr(2)); // 문제에서 주어진 숫자 int 변환
            dQ.push_back(num);
            sort(dQ.begin(), dQ.end()); // deque 퀵정렬
        }
        else if (oper[i][0] == 'D') {
            if (oper[i][2] == '1') {
                if (!dQ.empty()) dQ.pop_back();
            }
            else if (oper[i][2] == '-') {
                if (!dQ.empty()) dQ.pop_front();
            }
        }
    }
 
    if (dQ.empty()) {
        answer.emplace_back(0);
        answer.emplace_back(0);
    }
    else {
        answer.emplace_back(dQ.back());
        answer.emplace_back(dQ.front());
    }
    
    return answer;
}

 

---

 

 

 

 

정답코드 - priority_queue 사용

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> solution(vector<string> oper) {
    vector<int> answer;
 
    priority_queue<int> pQ; // 내림차순
    priority_queue<int, vector<int>, greater<int>> revpQ; // 오름차순
 
    for (int i = 0; i < oper.size(); i++)
    {
        if (oper[i][0] == 'I') { // 삽입
            int num = stoi(oper[i].substr(2)); // 숫자 추출
            pQ.push(num);
            revpQ.push(num);
        }
        else if (oper[i][0] == 'D') { // 삭제
            if (oper[i][2] == '1') {
                if (pQ.empty()) continue;
                if (!revpQ.empty() && pQ.top() == revpQ.top()) revpQ.pop(); // 최대 힙과 최소 힙의 최댓값이 같다면 최소 힙에서도 제거
                pQ.pop();
            }
            else if (oper[i][2] == '-') {
                if (revpQ.empty()) continue;
                if (!pQ.empty() && pQ.top() == revpQ.top()) pQ.pop(); // 최소 힙과 최대 힙의 최솟값이 같다면 최대 힙에서도 제거
                revpQ.pop();
            }
        }
 
        if (pQ.top() < revpQ.top()) // 만약 최대 힙의 최댓값이 최소 힙의 최솟값보다 작다면
        {
            while (!pQ.empty()) pQ.pop();
            while (!revpQ.empty()) revpQ.pop();
        }
    }
 
    if (pQ.empty() || revpQ.empty()) {
        answer.emplace_back(0);
        answer.emplace_back(0);
    }
    else {
        answer.emplace_back(pQ.top());
        answer.emplace_back(revpQ.top());
    }
 
    return answer;
}

 

 

---