(C++) - 프로그래머스(고득점 kit - 힙(heap)) : 이중우선순위큐 답

programmers.co.kr/learn/courses/30/lessons/42628

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

heap을 사용할 때 구현이 너무 복잡하고 자꾸 틀려서 deque로 O(100만log100만)로 풀게 되었습니다..

 

풀이방법

 1. I일 경우에는 넣을 때마다 deque를 오름차순으로 sort해줍니다.

 2. D일 경우 deque가 차 있다면 1일 때는 dq의 마지막을, -1일 때는 dq의 처음을 pop해주면 됩니다.

Code

#include <bits/stdc++.h>
using namespace std;

vector <int> solution(vector<string> operations){
    deque <int> dq;
    vector <int> answer;
    for(int i = 0; i < operations.size(); i++){
        int num = stoi(operations[i].substr(2));
        
        if(operations[i][0]=='I'){
            dq.push_back(num);
            sort(dq.begin(),dq.end());
        }else{
            if(!dq.size())continue;
            if(num == 1) dq.pop_back();
            else if(num == -1) dq.pop_front();
        }
    }
    if(!dq.size()){
        answer.push_back(0);
        answer.push_back(0);
    }else{
        answer.push_back(max(dq[0], dq[dq.size()-1]));
        answer.push_back(min(dq[0], dq[dq.size()-1]));
    }
    return answer;
}