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

코딩테스트 연습 - 이중우선순위큐

풀이

처음에는 D -와 D가 나올 때를 구분해서 각각의 priority_queue를 선언하여 사용하는 방법을 사용했다. 풀고 나서 맞았을 때 깜짝 놀랐다(조금은 막무가내 방법 같아서..ㅎㅎ)

맞추고 다른 풀이들을 보는데 multiset을 사용해서 푼 코드들이 많이 보였다. multiset은 사용해 본 적이 없어서 이걸 사용해서 문제를 다시 풀어봤다.
삽입과 동시에 정렬이 되는 구조이고, erase를 통해서 최대값, 최소값 삭제가 편리했다.
이 풀이가 다른 문제를 풀 때도 도움이 많이 될 것 같다(begin(), end()와 포인터 같이 사용, multiset 사용)

※ 공부하며 새롭게 배운 점!!!

s.begin() : set의 첫번째 원소를 가리키는 iterator
s.end() : set의 마지막 원소 다음을 가리키는 iterator

iterator가 가리키는 원소를 얻기 위해서 포인터(*)를 사용하면 된다!

*s.begin()
*--s.end()

코드

처음에 푼 방법

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

vector<int> solution(vector<string> operations) {
    vector<int> answer(2, 0);
    vector<int> v;
    
    for (auto o : operations) {
        if (o[0] == 'I') {
            int number = stoi(o.substr(2));
            v.push_back(number);
        } else {
            if (v.empty()) continue;
            
            if (o[2] == '-') { // 최솟값을 삭제합니다.
                priority_queue<int, vector<int>, greater<int>> pq1(v.begin(), v.end());
                pq1.pop();
                v.clear();
                
                while (!pq1.empty()) {
                    v.push_back(pq1.top()); pq1.pop();
                }
            } else { // 최댓값을 삭제합니다.
                priority_queue<int, vector<int>> pq2(v.begin(), v.end());
                pq2.pop();
                v.clear();
                
                while (!pq2.empty()) {
                    v.push_back(pq2.top()); pq2.pop();
                }
            }
            
        }
    }
    
    if (v.size() != 0) {
        sort(v.begin(), v.end());
        answer[0] = v.back();
        answer[1] = v.front();
    }
    
    return answer;
}

새롭게 공부한 방법

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

vector<int> solution(vector<string> operations) {
    vector<int> answer(2, 0);
    multiset<int> m;
    
    for (auto o : operations) {
        if (o[0] == 'I') {
            m.insert(stoi(o.substr(2)));
        } else {
            if (m.empty()) continue;
            
            if (o[2] == '-') { // 최솟값 삭제
                m.erase(*m.begin());
            } else { // 최대값 삭제
                m.erase(*--m.end());
            }
        }
        
    }
    
    if (!m.empty()) {
        answer[0] = *--m.end(); // 최대값
        answer[1] = *m.begin(); // 최소값
    }
    
    return answer;
}