컨테이너

이중우선순위큐

프로그래머스

 

오늘 프로그래머스의 이중우선순위 큐라는 문제를 풀었는데 문제의 이름에서 보이는 것처럼 나는 우선순위 큐를 두 개 활용해서 풀었다. 최댓값을 관리하는 우선순위 큐, 최솟값을 관리하는 우선순위 큐 총 두 개다.

 

// 작은 순서대로 정렬 / 큰 순서대로 정렬
    priority_queue<int, vector<int>, greater<int>> minpq;
    priority_queue<int, vector<int>> maxpq;
    
    // 반대편 원소 삭제시 잠시 대기시켜둘 큐
    queue<int> waitque;
    
    int size = 0;
    for(int i=0;i<operations.size();i++)
    {
        string tmp = operations[i];
        if (tmp[0] == 'I') {
            maxpq.push(stoi(tmp.substr(2)));
            minpq.push(stoi(tmp.substr(2)));
            size++;
        }
        else if(tmp[0] == 'D')
        {
            int type = stoi(tmp.substr(2));
            if (size > 0)
            {
                // 최대값 삭제 , 최소값 삭제
                if (type == 1) {
                    int tmp = maxpq.top();
                    maxpq.pop();
                    // 삭제 후 반대편 큐에서도 해당 내용 삭제
                    while(!minpq.empty())
                    {
                        if (tmp != minpq.top()) waitque.push(minpq.top());
                        minpq.pop();
                    }
                    while(!waitque.empty())
                    {
                        minpq.push(waitque.front());
                        waitque.pop();
                    }
                }
                else if (type == -1) {
                    int tmp = minpq.top();
                    minpq.pop();
                    while(!maxpq.empty())
                    {
                        if (tmp != maxpq.top()) waitque.push(maxpq.top());
                        maxpq.pop();
                    }
                    while(!waitque.empty())
                    {
                        maxpq.push(waitque.front());
                        waitque.pop();
                    }
                }
                size--;
            }
        }
    }

 

보다시피 코드가 매우 복잡하다.

아무래도 문제에 적혀있는 이름 때문에 꼭 우선순위 큐를 활용해야만 한다고 생각했는데 다 풀고 다른 사람들의 풀이를 보고 정말 한 가지에 얽매여있었음을 깨달았다.

 

C++에는 Vector, Map, Que, Set 등 유용한 컨테이너들이 많지만 나는 주로 vector와 map을 많이 사용했고 set은 정말 거들떠 보지도 않았다. 그냥 맨날 먹던 것만 먹는 격.

 

set은 정렬 상태를 유지해주며 que의 front와 stack의 top처럼 해당 컨테이너의 시작과 끝에 바로 접근할 수 있었다. 이때 사용되는 것은 다른 컨테이너들과 마찬가지로 begin()과 end()를 활용한다. 

특히나 기본적으로 set은 map과 같이 중복을 허용하지 않는 특성이 있는데 multiset으로 구현하면 중복을 허용하게도 구현할 수 있다. 그럼 set을 이용한 코드를 보자.

 

    // multiset으로 구현된 que
    multiset <int> que;
    
    for (int i=0;i<operations.size();i++) {
        string tmp = operations[i];
        int num = stoi(tmp.substr(2));
        if (tmp[0] == 'I') que.insert(num);
        else{
            if (num == 1){
                // 최대값 삭제
                auto it = que.end();
                // 큐가 비어있지 않다면 삭제
                if(que.size() > 0) {
                    it--;
                    que.erase(it);
                }
            }
            else{
                // 최소값 삭제
                auto it = que.begin();
                if (que.size() > 0) {
                    que.erase(it);
                }
            }
        }
    }

 

 

우선순위 큐를 이용해 구현했을 때는 중간에 큐를 여기로 옮기고 저기로 옮기느라 계속해서 시간과 자원을 낭비하는 방면 멀티셋은 그렇지 않고 있음을 알 수 있다.

 

사실 우선순위 큐 한 개만 이용해서도 위와 비슷하게 구현할 수는 있겠다는 생각이 들었지만 결국 우선순위 큐이기 때문에 다른 컨테이너로 값을 옮기고 삭제하는 작업이 필수적이라 다른 컨테이너를 사용하는 편이 시간상으로도 더 이득일 것 같다고 결론을 내렸다.

 

문제를 풀 때 좀 다양한 컨테이너를 사용해보면서 공부하는 편이 좋을 것 같다.