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

프로그래머스의 Lv.3 이중우선순위큐입니다.

문제 출처

이중우선순위큐

문제 해설

사실 이 문제의 정해는 문제에서 말하는 것처럼, 힙 두개를 사용해서 최대값 최소값을 구해야 한다.

그러나 결국 최대값과 최솟값을 구할꺼면, 배열로 해도 되지 않을까? 배열에 넣은 다음 정렬해버리면 아무 문제 없지 않나?

그래서 처음에는 vector로 문제를 풀려고 시도를 했으나, operation으로 “D 1”이 들어오면 제일 마지막 값을 빼버리면 되는데, “D -1”이 나오는 경우에는 앞의 값을 빼야해서 따로 포인터를 관리해서 계산해줘야 한다. 이렇게 풀 수도 있으나, cpp에서는 앞, 뒤 원소를 자유롭게 빼고 넣을 수 있는 deque 자료구조가 있어서 이걸로 풀었다.

풀이는 간단하다. “I” 명령이 들어올 때 마다, deque에 넣고, “D” 명령이 들어올 때 마다, 정렬한 후 값을 빼주면 된다.

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    deque<int> dq;
    for(auto operation : operations){
        char oper = operation[0];
        int num = stoi(operation.substr(2));
        if(oper == 'I'){
            dq.push_back(num);
        }else if(oper == 'D' && !dq.empty()){
            sort(dq.begin(),dq.end());
            if(num == 1){
                dq.pop_back();
            }else{
                dq.pop_front();
            }
        }
    }
    
    sort(dq.begin(),dq.end());
    
    if(dq.empty()){
        answer.push_back(0);
        answer.push_back(0);
    }else{
        answer.push_back(*(dq.end()-1));
        answer.push_back(*dq.begin());
    }
    
    return answer;
}