[C++] level3 이중 우선순위 큐 42628

📌이중 우선순위 큐

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

우선순위 큐를 2개 사용한다. 1개는 오름차순으로 정렬되는 큐, 1개는 내림차순으로 정렬되는 큐.
I연산이 일어날 때 숫자를 각 큐에 넣어주고,
D연산이 일어날 때 -1인 경우 오름차순 정렬 큐에서 가장 앞에 원소(최소값)을 빼주고,
1인 경우 내림차순 정렬 큐에서 가장 앞에 원소(최대값)을 빼준다.

주의할 점
I연산이 일어날 때 2개 큐에 값을 넣어주고 삭제 연산은 경우에 따라 1개씩 해준다.
ex. 3번 삽입이 일어나고 2번 D -1, 1번 D 1 일어났다고 가정할 때 오름차순 큐는 2개, 내림차순 큐는 1개 남는다. (균일하게 큐 사이즈를 갖지 못함)
큐 사이즈가 균일할 수 있도록 별도로 cnt 변수를 두어 0이 된 경우에 각 큐를 초기화 시켜줘야 한다.

📌코드

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

vector<int> solution(vector<string> operations)
{
    vector<int> answer(2, 0); //2개짜리 배열. 0으로 초기화

    priority_queue<int, vector<int>> pq_desc;              //내림차순 정렬
    priority_queue<int, vector<int>, greater<int>> pq_asc; //오름차순 정렬 (greater 사용 시 구현체 사용 꼭)
    int cnt = 0;                                           //q.size();

    for (auto oper : operations)
    {
        if (oper.at(0) == 'I')
        {                                   //삽입 명령 수행
            string number = oper.substr(2); //2번 idx부터 끝까지 숫자
            pq_desc.push(stoi(number));
            pq_asc.push(stoi(number));
            cnt++;
        }
        else
        { //삭제 명령 수행
            if (cnt == 0)
                continue; //큐가 비었는데 삭제 요청

            string number = oper.substr(2); //2번 idx부터 끝까지 숫자
            if (number == "1")              //최대값 삭제
                pq_desc.pop();
            else if (number == "-1") //최소값 삭제
                pq_asc.pop();

            cnt--; //q에서 삭제가 일어났으니
        }

        //만약 큐가 0이라면 desc, asc 모두 다 지워줌(균일하게 지워주기 위함)
        if (cnt == 0)
        {
            while (!pq_desc.empty())
                pq_desc.pop();
            while (!pq_asc.empty())
                pq_asc.pop();
        }
    }

    if (cnt)
    {                              //q에 값이 존재한다면
        answer[0] = pq_desc.top(); //최대값
        answer[1] = pq_asc.top();  //최소값
    }

    return answer;
}  

---

회고
풀이 중에 set을 이용한 분이 계셨다 ......
나는 이중 우선순위 큐라해서 우선순위 큐를 2개써서 풀어야겠다 라는 생각을 했다.
근데 중복 값 때문에 골치 아파서 결국 큐 사이즈를 삽입 시마다 count 하고, 큐가 0이라면 두 우선순위 큐를 초기화하는 식으로 풀었는데
애초에 set을 이용하면 이 부분은 쉽게 해결할 수 있는 부분이었다 .... 조금만 더 깊게 생각했으면 좋았을텐데 ... 잉 바보
그래도 풀어낸거에 ... 의의를 두고 .. 다음에 다시 풀 때 발전하면 되지 !!