프로그래머스 - 이중우선순위큐(Lv.3)

문제풀이

• max heap, min heap 에 대한 문제인데, 덱(deque)을 통해 앞뒤 요소를 쉽게 다룰 수 있었다.
• Algorithm 헤더파일 내에 sort 함수를 호출하여 시간 복잡도를 최대한 줄이고자 하였으나, 최악의 경우가 들어온다면 시간초과가 날 수도 있을 것 같다.
• 본 문제에서는 stringstream 을 활용하여 문자열을 파싱하는 법을 익히도록 하자.

구현(All Pass)

#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <sstream>
#include <iostream>

using namespace std;

bool cmp(int a, int b){
    return a<b;
}
void update_queue(string operations, deque<int>& deq){
    stringstream stm;
    stm.str(operations);
    char op; int num;
    stm >> op >> num;
    getchar();
    
    switch(op){
        case 'I':
            cnt++;
            deq.push_back(num);
            sort(deq.begin(), deq.end(), cmp);
            break;
        case 'D':
            if(num==-1){ // 최솟값을 지운다.
               if(deq.size()==0) break;
                deq.pop_front();
            }
            else if(num==1){ // 최댓값을 지운다.
               if(deq.size()==0) break;
                deq.pop_back();
            }
    }
}

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    deque<int> deq;
    
    for(int i=0; i<operations.size(); i++){
        update_queue(operations[i], deq);
    }
    
    if(deq.size()==0){
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        answer.push_back(deq.back());
        answer.push_back(deq.front());
    }
    
    return answer;
}