이중우선순위큐

문제

---

문제의 시간 복잡도

$O(n)$ 이하의 풀이를 해야 한다고 생각을 하였다.

---

풀이

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


using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer = {0,0};
    deque<int> q;
    
    for(int i=0;i<operations.size();i++)
    {
        if(operations[i].substr(0,1)=="I")
        {
            string s=operations[i].substr(2,operations[i].size()-2);
            int x = stoi(s);
            q.push_back(x);
            sort(q.begin(),q.end());
        }
        else if(!q.empty())
        {
            if(operations[i] == "D -1")
            {
                q.pop_front();
            }
            else
            {
                q.pop_back();  
            } 
        }
    }
    if(!q.empty())
    {
        deque<int>::iterator iter;
        iter = --q.end();
        answer[0] = *(iter);
        iter = q.begin();
        answer[1] = *(iter);
    }
    return answer;
}

// -45 333

// time complexity = n

---

문제의 첫번째 접근법

두개의 priority queue를 생성하여 최소힙 최대힙을 각각 관리한다.

하지만 이것은 문제를 제대로 파악하지 못하여서 이런 생각을 했다.

이중 우선순위 큐라고 하여서 큐 내부에 큐가 있는 구조라고 생각을 하고 이런식으로 접근을 했는데 문제를 잘못 이해한 풀이였다.

---

문제의 두번째 접근법

문제를 보면 첫번째 부분의 pop 연산과 마지막 부분의 pop연산이 있으므로 이에 대해서 시간복잡도가 상수 시간안에 끝나는 deque를 이용하면 좋겠다 생각을 했다.

그래서 문자열에서 I를 확인하면 push를 한 이후에 sort를 하게끔 했다.
그런데 이 부분이 deque에서는 sort를 할 때마다 $O(nlogN)$이 걸려서 비효율적인 구조라고 생각이 들었다. 이부분을 어떻게든 priority queue로 관리를 하게끔 하는 것이 더 좋은 코드 같은데 방법을 찾지는 못하였다.

그리고 I를 찾지 못하는 경우에는 먼저 deque가 비어있는지를 확인을하고 비어있지 않다면 최소힙 최대힙에 대해서 판별을 한 후, 첫 요소를 삭제할지 마지막 요소를 삭제할지 결정을 안후 삭제를 한다.

마지막에는 deque의 상태를 확인하고 answer의 요소값을 변경해준다.

---

기타사항

container의 end()는 마지막요소 다음, 즉 빈 공간의 iterator이다.

substr의 인수는 (시작점, 개수) , 즉 시작점으로부터 몇개를 자를지이다.

multiset 이라는 container는 중복된 값의 push를 허용하고, 값이 push가 되면 오름차순으로 정렬을 한다.