프로그래머스 이중우선순위큐 c++ // pq, multiset 사용법

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

프로그래머스

1. 우선순위큐 의사코드

1. 문제점 : 큐2개를두면, 실제 최대힙에서는 삭제되어도 최소힙에서는 삭제가 안되므로 제대로 비었는지 확인이 안된다

-> 해결 : cnt 변수 정의 //현재 큐에 있는원소의 갯수

2. 시키는대로 연산 구현후, cnt==0이면 실제로 pq1, pq2의 원소를 다 뺴주어야한다! (tc1번 걸림)

 

2. 우선순위큐 전체코드

#include <bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>> pq1;
priority_queue<int,vector<int>,greater<int>> pq2;

vector<string> split(string s, string deli){
    vector<string> ret;
    long long pos=0;
    while((pos = s.find(deli))!=string::npos){
        string token = s.substr(0,pos);
        ret.push_back(token);
        s.erase(0,pos+deli.size());
    }
    ret.push_back(s);
    return ret;
}
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<int> deleted;
    // vector<string> v = split("D -1"," ");
    // for(auto s : v) cout<<s<<" ";
    
    int cnt=0; // 현재 큐에들어있는 원소갯수
    for(auto operation : operations){
        vector<string> v = split(operation," ");
        if(v[0]=="I"){
            pq1.push(stoi(v[1]));
            pq2.push(stoi(v[1]));
            cnt++;
            continue;
        }
        else if(v[0]=="D"){
            if(cnt==0) continue; //빈큐에 삭제명령시 패스
            if(v[1]=="1"){
                if(pq1.empty()) continue;
                pq1.pop();
                cnt--;
            }
            if(v[1]=="-1"){
                if(pq2.empty()) continue;
                pq2.pop();
                cnt--;
            }
            if(cnt==0){ //갯수가0개라면, 남은원소 실제로 모두빼주기!!
                while(pq1.size()) pq1.pop();
                while(pq2.size()) pq2.pop();
            } 
        }
    }

    if(cnt==0) return {0,0};
    return {pq1.top(),pq2.top()};
    return answer;
}

 

3. 멀티셋 풀이

그냥 양쪽에서 접근가능한 pq라고 보면될듯하다.

ms.begin, ms.end, ms.insert로 접근/삽입한다.

주의 : 기본정렬이 오름차순이다 (1, 2, 3, 4..)

#include <bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>> pq1;
priority_queue<int,vector<int>,greater<int>> pq2;
multiset<int> ms;

vector<string> split(string s, string deli){
    vector<string> ret;
    long long pos=0;
    while((pos = s.find(deli))!=string::npos){
        string token = s.substr(0,pos);
        ret.push_back(token);
        s.erase(0,pos+deli.size());
    }
    ret.push_back(s);
    return ret;
}
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<int> deleted;
    // vector<string> v = split("D -1"," ");
    // for(auto s : v) cout<<s<<" ";
    
    int cnt=0; // 현재 큐에들어있는 원소갯수
    for(auto operation : operations){
        vector<string> v = split(operation," ");
        if(v[0]=="I"){
            ms.insert(stoi(v[1]));
            continue;
        }
        else if(v[0]=="D"){
            if(ms.empty()) continue;
            if(v[1]=="1"){
                 ms.erase(--ms.end()); //기본이 오름차순임..
                //ms.erase(ms.begin());
            }
            if(v[1]=="-1"){
                ms.erase(ms.begin());
                //ms.erase(--ms.end());
            }
        }
    }

    if(ms.size()==0) return {0,0};
    return {*(--ms.end()),*ms.begin()};
    return answer;
}