[C++]이중우선순위큐

요약

• dequeue를 사용하기
• 문자열 자르기, 비교, 정수화
• sort

풀이과정

최대 최소값이 필요하며 최대 최소값을 pop한다. -> 오름차순 정렬하는 dequeue

C++의 덱은 deque로 선언한다.

1. 자료형 결정

deque<int> deq;

2. 반복문 및 조건 설정

1. 명령어 자르기, 비교 및 정수화

맨 첫번째 문자로 D과 I를 판별하고, op.substr(2)를 통해 2~끝까지 숫자 영역을 자를 수 있다.

이를 stoi로 int형으로 변환한다.

2. 정렬 타이밍

삽입할 때마다 매번 sort하기보다는, 삭제를 할 때 정렬하는 방법을 생각했다.

단, 삭제가 연속으로 일어난 경우도 정렬할 필요가 없다.

이를 위해 outdated 라는 bool 변수를 기본값 true로 선언한다.(첫 정렬은 무조건 일어나게 하려고)

삽입이 일어나면 outdated는 true가 되며, 

삭제를 하기 직전에 outdated가 true이고 size가 1보다 크다면 정렬을 한다.

    for(string op : operations)
    {
        if(op[0] == 'I')
        {
            deq.push_back(stoi(op.substr(2)));
            outdated = true;
        }
        else if(!deq.empty())    // D이면서 deq가 비어있지 않음
        {
            if(outdated && deq.size() > 1)  
            {
                sort(deq.begin(),deq.end());
                outdated = false;
            }
            
            if(op[2] == '1')   //최댓값 삭제 - back
            {
                deq.pop_back();
            }
            else    //최솟값 삭제 - front
            {
                deq.pop_front();
            }
        }
    }

3. 값 도출하기

이후, outdated 된 채로 끝났을 수 있기 때문에, outdated 인 경우 정렬하도록 하고,

size의 크기에 따라 0을 반환할지, 최대최소를 반환할지 조건을 나눠 값을 answer에 저장한다.

    if(outdated)
        sort(deq.begin(),deq.end());

    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;

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    deque<int> deq;
    bool outdated = true;  //sort 횟수를 줄이기 위해
    
    for(string op : operations)
    {
        if(op[0] == 'I')
        {
            deq.push_back(stoi(op.substr(2)));
            outdated = true;
        }
        else if(!deq.empty())    // D이면서 deq가 비어있지 않음
        {
            if(outdated && deq.size() > 1)  
            {
                sort(deq.begin(),deq.end());
                outdated = false;
            }
            
            if(op[2] == '1')   //최댓값 삭제 - back
            {
                deq.pop_back();
            }
            else    //최솟값 삭제 - front
            {
                deq.pop_front();
            }
        }
    }


    if(outdated)
        sort(deq.begin(),deq.end());

    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;
}

다른 사람의 풀이

1. multiset container 활용하기

multiset<int> ms;

multiset을 잘 몰라서 정리해봤다. 한줄요약하자면 중복값이 보존되면서 자동 정렬되는 container이다.

set의 경우 중복값이 제거되지만, multiset은 중복값이 제거되지 않는다.

그러면서 정렬이 되니, 이 문제에 적합해보인다.

삽입

ms.insert(stoi(op.substr(2)));

삽입될때마다 자동 정렬된다.

삭제

ms.erase(--ms.end());
ms.erase(ms.begin());

맨 뒤 값의 주소는 .end()에서 1을 뺀 값

맨 앞 값의 주소는 .begin()

값 가져오기

*(--ms.end())
*ms.begin()

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    
    for(string op : operations)
    {
        if(op[0] == 'I')
            ms.insert(stoi(op.substr(2)));
        else if(!ms.empty())
        {
            if(op[2] == '1')  //최댓값 삭제 - end
                ms.erase(--ms.end());
            else    //최솟값 삭제 - begin
                ms.erase(ms.begin());
        }
        
        // for(auto a : ms)
        //     cout << a << " ";
        // cout << endl;
    }
    
    if(ms.size() == 0)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(*(--ms.end()));
        answer.push_back(*ms.begin());
    }
    return answer;
}

정렬을 삽입때마다 할 테니, 시간이 조금 더 걸리는 듯 하다.