[프로그래머스] 3단계 - 이중우선순위큐

1. 문제 설명

이중 우선순위큐가 할 연산이 매개변수로 주어질 때, 모든 연산을 처리한 후 [최댓값, 최솟값]을 return

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

프로그래머스

 

2. 문제 풀이법

문제 제목부터 주어진 우선순위 큐로 문제를 해결하는 방법이 있고, 그냥 벡터로 푸는 방법 2가지가 있다

 

우선 우선순위 큐로 푸는 방법은 최소값을 기준으로 하는 우선순위 큐와, 최대값을 기준으로 하는 우선순위 큐 2개가 필요하다

만일 I 명령어가 주어지면 최소값 큐와, 최댓값 큐에 각각 값을 집어 넣는다

이때 큐에 숫자가 몇개가 들어가 있는지 count 해주어야 한다

그러면 우선순위 큐이기 때문에 자동으로 정렬해준다

만일 4, -1, 10이라는 숫자를 넣는다면 최소값 우선순위 큐는 -1, 4, 10의 순서대로 값이 들어가 있을 것이고, 최대값 우선순위 큐는 10, 4, -1의 순서대로 값이 들어가 있을 것이다

 

이제 D 명령어가 주어졌을때 1이면 최대값을 빼는 것이므로, 최대값 우선순위 큐를 pop 해준다

-1이면 반대로 최소값 우선순위 큐를 pop 해준다

10이라는 숫자를 뺀다고 했을때, 최대값 우선순위 큐는 4, -1이 들어가 있을 것이고, 최소값 우선순위큐는 -1, 4, 10 그대로 값이 들어가 있을것이다

삭제 연산을 하면 각 우선순위큐에 들어있는 숫자가 다를것이다

이때 큐에 숫자가 몇개 들어가있는지 count해주는 변수를 통해서 관리를 해주면 된다

만일 큐에 숫자가 0개가 들어가 있으면 2개의 우선순위 큐를 모두 비워주는 처리를 따로 해주어야 한다

 

모든 연산 이후 큐에 숫자가 0개이면 [0, 0]이 return되게 한다

만일 숫자가 1개라면 [최댓값, 0] 혹은 [0, 최솟값]으로 return 되게 한다

숫자가 2개 이상이라면 [최댓값 우선순위큐 top, 최솟값 우선순위큐 top]으로 return 되게 한다

 

 

vector로 푸는 방법은 더 간단하다

I가 들어오면 그냥 숫자를 push 해주면 되고, D가 들어오면 sort해준다

이후 1이면 벡터의 맨 뒤의 숫자를, -1이면 벡터의 맨 앞의 숫자를 erase 해주면 된다

 

출력은 위의 방법과 동일하다

 

3. 소스 코드

priority_queue를 사용한 방법

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


using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int, vector<int>, greater<int>> q_min;
    priority_queue<int, vector<int>, less<int>> q_max;
    int queue_size = 0;
    
    for (int i = 0; i < operations.size(); i++) {
        string str = operations[i];
        
        if (str[0] == 'I') {
            string value = str.substr(2, str.size());
            int num = stoi(value);
            
            q_min.push(num);
            q_max.push(num);
            queue_size++;
        
        } else if (str[0] == 'D') {
            if (queue_size == 0)
                continue;
            
            if (str[2] == '1')
                q_max.pop();
            else
                q_min.pop();
            
            queue_size--;
            
            if (queue_size == 0) {
                while (!q_min.empty())
                    q_min.pop();
                
                while (!q_max.empty())
                    q_max.pop();
            
            }
        }   
    }
    
    if (queue_size == 0) {
        while (!q_min.empty())
                q_min.pop();
                
        while (!q_max.empty())
                q_max.pop();
    }
            
    
    
    if (queue_size == 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else if (queue_size == 1) {
        int num;
        
        if (q_min.empty())
            num = q_max.top();
        else
            num = q_min.top();
        
        if (num < 0) {
            answer.push_back(0);
            answer.push_back(num);
        }
        else {
            answer.push_back(num);
            answer.push_back(0);
        }
    }
    else {
        answer.push_back(q_max.top());
        answer.push_back(q_min.top());
    }
    
    return answer;
}CPP

 

vector를 사용한 방법

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    vector<int> v;
    
    for (int i = 0; i < operations.size(); i++) {
        string str = operations[i];
        
        if (str[0] == 'I') {
            string value = str.substr(2, str.size());
            int num = stoi(value);
            
            v.push_back(num);
        
        } else if (str[0] == 'D') {
            if (v.empty())
                continue;
            
            sort(v.begin(), v.end());
            if (str[2] == '1')
                v.erase(v.end() - 1);
            else
                v.erase(v.begin());
        }   
    }
    
    sort(v.begin(), v.end());
    
    if (v.size() == 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else if (v.size() == 1) {
        if (v.front() < 0) {
            answer.push_back(0);
            answer.push_back(v.front());
        }
        else {
            answer.push_back(v.front());
            answer.push_back(0);
        }
    }
    else {
        answer.push_back(v.back());
        answer.push_back(v.front());
    }
    
    return answer;
}CPP