[코딩테스트 C++] 이중우선순위큐

오늘의 문제

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

이중우선순위큐

나의 풀이

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<string> cmd = {"D 1", "D -1"};
    priority_queue<int, vector<int>, less<int>> pql; // 내림
    priority_queue<int, vector<int>, greater<int>> pqg; // 오름
    int cnt = 0;
    
    for(int i=0;i<operations.size();i++){
        string s = operations[i];
        if(cnt == 0){ // 비우기
            while(!pql.empty())
                pql.pop();
            while(!pqg.empty())
                pqg.pop();
        }
        if(s == cmd[0]){ // 최댓값
            if(cnt != 0){
               pql.pop();
                cnt--;
            }
        }else if (s == cmd[1]){ // 최솟값
            if(cnt != 0){
               pqg.pop();
                cnt--;
            }
        }else{ // 숫자 push
            int num = stoi(s.substr(2, s.size()-2));
            pql.push(num);
            pqg.push(num);
            cnt++;
        }
    }
    if(cnt == 0)
        return {0, 0};
    else
        return {pql.top(), pqg.top()};
}

모범 답안

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> arguments) {
    vector<int> answer;
    multiset<int> que;
    multiset<int>::iterator iter;
    string sub;

    for(auto s : arguments) {
        sub =s.substr(0, 2);
        if(sub=="I ") que.insert(stoi(s.substr(2,s.length()-2))); 
        else if(s.substr(2,1)=="1"&&que.size()>0) { que.erase(--que.end()); }
        else if(que.size()>0) { que.erase(que.begin()); }
    }

    if(que.size()==0) { answer.push_back(0); answer.push_back(0); }
    else { 
        iter = --que.end(); answer.push_back(*iter); 
        iter = que.begin(); answer.push_back(*iter);
    }

    return answer;
}

배울 점

• 입력에서 모두 삭제한 후 추가할 때 벌어지는 경우를 생각하지 못해 결국 테스트에대한 입력 질문을 보게 되었다.
• 모든 입력의 경우를 생각할 수 있어야겠다.

• multiset을 처음 봤다. 정렬도 되고 중복되 된단다 ㄷ ㄷ
• set 과 같이 key 값 저장, 원소를 삽입하면 자동으로 정렬
• 연산자는 set과 동일. insert의 return 값이 pair가 아닌, 위치값이 반환(중복이 허용되기 때문)
• 엄청 유용할것 같다. 와

배운것 활용

• multiset을 사용하니 이렇게 코드가 간단해진다

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    
    for(auto o : operations){
        if(o == "D 1" && ms.size()>0){
            ms.erase(--ms.end());
        }else if(o == "D -1" && ms.size()>0){
            ms.erase(ms.begin());
        }else if(o[0] == 'I'){
            ms.insert(stoi(o.substr(2, o.size()-2)));
        }
    }
    if(ms.size() == 0)
        return {0, 0};
    else
        return {*(--ms.end()), *ms.begin()};
}