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

문제 링크

1. 문제 접근 과정🧐

1. 우선순위 큐는 최대, 최소를 동시에 관리할 수 없으므로 최댓값과 최솟값을 각각 따로 우선순위 큐를 둠
2. 중복한 데이터가 들어올 수 있으므로 map으로 들어온 수와 횟수를 저장
3. 각 명령에 따라 삽입, 최댓값 삭제, 최솟값 삭제
4. 큐의 값이 남아있는지 체크하여 답으로 반환

2. 시행착오🤯

• 삭제 시에 각 큐의 동기화를 제대로 하지 못해 잘못된 결과가 나와 실패했다.
  • 3, 5, 5가 있다면 최솟값 삭제 시 3이 없어지는데 최대값 큐에는 3이 남아 있어 이건 더미 데이터가 되어 잘못된 값이 나올 수 있다.
  • 중복값이 여러 개면 모두 지워버리는 불참사가 날 수도 있다.
    

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;
    for(string op : operations){
        char command = op[0];
        if(command == 'I'){
            string n;
            for(int i = 2; i < op.length(); i++) n += op[i];
            int num = stoi(n);
            max_pq.push(num);
            min_pq.push(num);
        }
        else if(command == 'D'){
            string n;
            for(int i = 2; i < op.length(); i++) n += op[i];
            if(n == "-1"){
                if(min_pq.empty()) continue;
                int min = min_pq.top();
                min_pq.pop();
                while(!max_pq.empty() && max_pq.top() == min) max_pq.pop();
            }
            else if(n == "1"){
                if(max_pq.empty()) continue;
                int max = max_pq.top();
                max_pq.pop();
                while(!min_pq.empty() && min_pq.top() == max) min_pq.pop();
            }
        }
    }
    if(max_pq.empty() || min_pq.empty()) for(int i = 0; i < 2; i++) answer.push_back(0);
    else answer.push_back(max_pq.top()), answer.push_back(min_pq.top());
    return answer;
}

3. 개선한 코드😄

• map을 활용하여 삽입된 수의 횟수를 저장하여 동기화를 하여 해결
  • 삭제 시에 더미 데이터를 제거하고 실제 값을 pop
  • 마지막에 한번 더 더미 데이터를 방지하기 위해 한번 더 제거 수행
    

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;
    map<int, int> m;
    for(string op : operations){
        char command = op[0];
        int num = stoi(op.substr(2));
        if(command == 'I'){
            max_pq.push(num);
            min_pq.push(num);
            m[num]++;
        }
        else if(command == 'D'){
            if(num == -1){
                while(!min_pq.empty() && m[min_pq.top()] == 0) min_pq.pop();
                if(!min_pq.empty()){
                    m[min_pq.top()]--;
                    min_pq.pop();
                }
            }
            else if(num == 1){
                while(!max_pq.empty() && m[max_pq.top()] == 0) max_pq.pop();
                if(!max_pq.empty()){
                    m[max_pq.top()]--;
                    max_pq.pop();
                }
            }
            while(!max_pq.empty() && m[max_pq.top()] == 0) max_pq.pop();
            while(!min_pq.empty() && m[min_pq.top()] == 0) min_pq.pop();
        }
    }
    if(max_pq.empty() || min_pq.empty()) for(int i = 0; i < 2; i++) answer.push_back(0);
    else answer.push_back(max_pq.top()), answer.push_back(min_pq.top());
    return answer;
}

4. 회고💭

• 2가지의 큐로 관리하는 방법은 생각했지만 중복된 수가 들어오는 것을 고려하지 못했고 2가지 큐를 동기화하는 방법도 잘못됐었다.
• 다양한 케이스를 생각할 수 있어야겠고 자료구조 공부를 더 해야 하며 조건이나 동기화를 코드로 구현하는 연습이 필요하다.