[프로그래머스 LV3] - 이중우선순위큐(priority queue) c++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

접근방법

sort함수의 시간 복잡도는 nlog(n)으로 알고 있다.

 

그러면 priority_queue만드는 거랑

넣을 때마다 sort()를 호출하는 거랑 시간복잡도는 비슷하다.

 

sort를 사용해서 deque도 정렬할 수가 있었다.(정말 편리하다)

 

함수의 리턴타입이 vector였는데,

return {0,0};

이 가능했다. vector도 {}로 초기화할 수 있는 걸 알았다.

 

 

코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    deque<int> pq;
    
    for (auto& o : operations) {
        if (o[0] == 'I') {
            int temp = stoi(o.substr(2));
            pq.push_back(temp);
        } else if (o[0] == 'D' && !pq.empty()) {
            if (o[2] == '1') pq.pop_back();
            else pq.pop_front();
        }
        sort(pq.begin(), pq.end());
    }
    
    if (pq.empty()) return {0,0};
    
    answer.push_back(pq.back());
    answer.push_back(pq.front());
    return answer;
}

개선할 점

priority_queue로 해결할 수 있는 방법을 찾아보자.....했는데, 안 보인다.