이중우선순위 큐

코드

[ priority_queue 풀이 ]

#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <iostream>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    int cnt=0;

    /* 2개의 우선순위 큐를 두어 내림차순, 오름차순으로 각각 관리
       --> 삽입은 둘다해주고, 최대값 삭제는 내림차순 큐에서, 최소값 삭제는 오름차순 큐에서!
         --> 어떻게 가능?
             : 각 큐에 전체적인 순서는 문제가 되지만, 최대,최소는 각각 계속 연산하며 관리하기 때문에
               최대, 최소만 각 큐에서 뽑는 이 문제의 경우 가능한 것! */
    priority_queue<int> pq; // 내림차순
    priority_queue<int, vector<int>, greater<int>> pq2; // 오름차순 
    char c; int n;
    for(int i=0;i<operations.size();i++)
    {
        stringstream ss(operations[i]);
        ss >> c;
        ss >> n;
        if(cnt == 0)
        {
            while(!pq.empty()) pq.pop();
            while(!pq2.empty()) pq2.pop();
        }
        if(c == 'I'){
            pq.push(n);
            pq2.push(n);
            cnt++;
        }else{
            if(n == 1 and cnt != 0){
                pq.pop();
                cnt--;
            }else if(n == -1 and cnt != 0){
                pq2.pop();
                cnt--;
            }
        }
    }
    if(cnt == 0) {
        answer.push_back(0);
        answer.push_back(0);
    }else{
        answer.push_back(pq.top());
        answer.push_back(pq2.top());
    }
    return answer;
}

• 처음
  : 우선순위 큐 2개(내림차순, 오름차순)으로 유지했을 때 순서가 바뀌면서 최대, 최소값도 달라져서 쓰지 못할것이라고 생각함
• 결과
  : 각 큐의 전체적인 순서는 보장이 안되지만, 최대,최소는 각각 관리하기 때문에 최대,최소 만큼은 2개의 큐의 연산에서 보장이 된다!!
• 주의할 점
  : cnt==0일때 2개의 큐를 모두 비워줘야 하는것!

---

[ multiset 풀이 ]

#include <string>
#include <vector>
#include <set>
#include <sstream>
#include <iostream>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    int cnt=0;
    multiset<int, less<int>> ms; // 오름차순
    char c; int n;
    for(int i=0;i<operations.size();i++)
    {
        stringstream ss(operations[i]);
        ss >> c;
        ss >> n;
        if(c == 'I')
            ms.insert(n);
        else{
            if(n == 1 and !ms.empty())
                ms.erase(--ms.end());
            else if(n == -1 and !ms.empty())
                ms.erase(ms.begin());
            }
    }
    if(ms.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }else{
        answer.push_back(*(--ms.end()));
        answer.push_back(*ms.begin());
    }
    return answer;
}

• multiset을 활용하면 좋은점
  • 자동 정렬
  • 삭제 위치 자유로움(iter 존재)
  • 중복값 허용 (set은 중복값 허용 X)
• multiset 주의할 점
  • multiset<int, greater<int>> ms : 내림차순
  • multiset<int, less<int>> ms : 오름차순(생략가능)
  • 가장 마지막 원소 삭제시 --> --ms.end() 해야함!
    (ms.end()는 가장 마지막 원소 다음 빈곳을 가리키고 있기 때문)