[ 프로그래머스 이중 우선순위 큐 (Lv3) ] (C++)

프로그래머스의 이중 우선순위큐(Lv3) 문제이다.

[ 문제풀이 ]

주어진 연산에 맞게 큐에 값을 넣거나 빼는 연산을 진행해야 하는 문제이다.

본인은 'Dequeue'를 이용해서 이 문제에 접근하였다.

문제를 풀기에 앞서 'Dequeue'에 관해서 간략하게만 알아보자.

# Dequeue

Dequeue는 Queue와 굉장히 유사한 자료구조이다.

Queue는 '선입선출(FIFIO)'의 구조를 가지고 있다. 그래서 값을 무조건 뒤로만 넣을 수 있고, 값을 빼내올 때는 무조건 가장 앞에 있는 값만 뺄 수가 있다.

하지만 Dequeue는 양방향 입출이 가능하다. 원하면 가장 앞에 값을 넣을 수도 있고, 가장 뒤에 값을 넣을수도 있다.

즉 ! push_front(), push_back(), pop_front(), pop_back()과 같은 함수들이 존재한다.

또한, Queue는 begin()과 end()를 가르키는 함수가 없지만, Dequeue의 경우에는 begin()과 end()를 가르키는 함수가 존재하기 때문에 이런 면에 있어서도 접근이 더욱 용이한 자료구조이다.

그럼 문제를 풀어보자.

# Case1 : 명령어 'I'가 들어온 경우

이 경우에는 I 뒤에 있는 숫자를 선언해놓은 Dequeue에 삽입해 주면 된다.

가장 앞에 삽입을 하든, 가장 뒤에 삽입을 하든 상관이 없다. 하지만 ! 우리는 이후에 알아볼 'D'라는 명령어가 나올 경우, 최댓값, 최솟값을 찾아내야 하기 때문에, 본인은 값을 삽입할 때 마다, Dequeue를 정렬을 시켜 주었다.

이 부분에서 위에서 언급한, begin()과 end() 함수를 이용해서 sort() 함수를 용이하게 사용할 수 있다.

# Case2 : D 1

이 경우에는 현재 큐에서 가장 큰 값을 삭제해야 하는 것이다.

우리는 이미 값을 넣을 때 마다, 정렬을 통해서 가장 큰 값이 가장 뒤에 오도록 만들어 놓았다.

간편하게, pop_back()을 통해서 최댓값을 삭제할 수 있다.

# Case3 : D -1

이 경우도 마찬가지이다. 이미 오름차순으로 정렬이 되어있기 때문에, pop_front()라는 함수를 통해서 가장 앞에 있는 값을 삭제해 주면 최솟값을 삭제하는 것과 같은 효과를 볼 수 있다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
vector<int> solution(vector<string> operations) 
{
    vector<int> answer;
    deque<int> Q;
    for (int i = 0; i < operations.size(); i++)
    {
        char C = operations[i][0];
        string Temp = "";
        for (int j = 2; j < operations[i].length(); j++) Temp = Temp + operations[i][j];
        int Num = stoi(Temp);
 
        if (C == 'I')
        {
            Q.push_back(Num);
            sort(Q.begin(), Q.end());
        }
        else
        {
            if (Q.empty() == true) continue;
            if (Num == 1) Q.pop_back();
            else Q.pop_front();
        }
    }
 
    if (Q.empty() == true)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(Q.back());
        answer.push_back(Q.front());
    }
 
    return answer;
}