프로그래머스 이중순위우선큐 C++

문제 설명 

 

입출력 예

operations                                                                                                                                              return

["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최댓값 7, 최솟값 5를 반환합니다.

 

#include <string>
#include <vector>
#include <queue> 
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector<int> doublePq; 
    
    
    for(string s : operations)
    {
        
        string sPart = s.substr(2);
        int tmp = stoi(sPart);

        
        if(s[0] == 'I') //숫자삽입
        {
            doublePq.push_back(tmp);
            sort(doublePq.begin(), doublePq.end()); //오름차순
        }
        else//삭제하는 경우
        {
            if(doublePq.size() == 0) continue;
            if(tmp == 1) //최대값 삭제
            {
               doublePq.erase(doublePq.begin() + (doublePq.size()-1));
            }
            if(tmp == (-1) ) //최소값 삭제
            {
                doublePq.erase(doublePq.begin());
            }
            
        }
        
    }
    if(doublePq.empty()) 
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
    answer.push_back(doublePq.back());
    answer.push_back(doublePq.front());
    }
        return answer;
}

 

=> HEAP에 포함되어있는 문제이길래 maxHeap과 minHeap을 사용해서 풀려다가 더 간단한 방법을 생각해보았습니다. 

=> vector를 이용하는 방법입니다. 

=>  'I'인 경우무조건 값을 PUSH_BACK 합니다. 이후 sorting을 합니다. 

(해당 단계에서 시간초과가 뜰 줄 알았는데 뜨지 않았습니다.) 

=> 'D'인경우 '1'인 경우 max값을, '-1'인 경우 min값을 제거해주었습니다. 

(이미 sorting되어있는 vector이므로 정렬순서에 따라 맨 앞과 맨뒤를 빼주면 됩니다.) 

* 이부분에서 vector의 <begin(), end()> 와 <front(), back()> 이 '포인터'와 '값'을 나타내는 것을 염두에 두어야 합니다.