[프로그래머스] [C++] 이중우선순위큐 (sort, bst, map)

1. 문제  

이중 우선순위 큐는 다음 연산을 할 수 있다.

 

| 숫자 : 큐에 주어진 숫자를 삽입

D 1:     큐에서 최댓값을 삭제

D -1:    큐에서 최솟값을 삭제

 

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질때.

 

모든 연산을 처리한 후 큐가 비어있으면 [0, 0]

비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현하여라.

 

operationsd의 원소는 "명령어 데이터" 형식으로 만약 최댓값/최솟값을 삭제하는 연산에서 

    최댓값/ 최솟값이 둘 이상인 경우, 하나만 삭제한다.

 

빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시한다.

 

 

 

2. insertionSort를 활용한 풀이

바이너리 서치 트리를 구현해서 문제를 해결할 수 있지만

균형잡힌 바이너리 서치 트리는 구현이 복잡하기 때문에 

정렬된 상태에서 최고의 성능을 발휘하는 삽입정렬을 사용하여 문제를 해결하였다.

 

삽입의 경우 이진 검색으로 자리를 찾을 수 있지만

배열에서의 삽입은 공간을 만들어야하므로

insertion 이 더 빠를 것이다.

 

#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
 
using namespace std;
 
void insertionSort(vector<int>::iterator first, vector<int>::iterator last) {
    while(first != --last) {
        if(*last < *(last-1))
            iter_swap(last, (last -1));
        else 
            break;
    }
}
 
vector<int> solution(vector<string> operations) {
    vector<int> vq;
    int minIdx = 0;
    for(int i = 0; i < operations.size(); i++)
    {
        if(operations[i][0] == 'D') {
            if(minIdx >= vq.size())
                continue;
            if(operations[i][2] == '-')
                minIdx++;
            else 
                vq.pop_back();
        }
        else {
            vq.push_back(stoi(operations[i].substr(2)));
            insertionSort(vq.begin() + minIdx, vq.end());
        }
    }
    if(minIdx >= vq.size())
        return {0, 0};
    return {vq.back(), vq[minIdx]};
}
 

 

insertion sort를 사용한 풀이

 

3. 균형 잡힌 이진 검색 트리 사용

균형잡힌 이진 검색 트리가 내부적으로 구현되어 있는 set 이나 map을 활용 하지 않은것,

 

특히 multiset을 이용하면 문제가 쉽게 해결된다.

 

이 경우 begin 에 최소, --end 에 최대 값이 들어가게 된다.

 

 

다음 코드는 map을 활용한 코드이다.

set을 사용하면 훨씬 코드가 간결하지만,

다른 사람 풀이에 multiset으로 풀이한게 있기 때문에

그냥 map으로 구현해보았다.

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
vector<int> solution(vector<string> arguments) {
    vector<int> answer;
    map<int, int> que;
 
    for(auto s : arguments) {
        if(s[0] == 'I')
            que[stoi(s.substr(2))]++; 
        else if(s[2] == '1' && que.size()>0) { 
            if(que[(--que.end())->first] == 1)
                que.erase((--que.end())->first);
            else 
                que[(--que.end())->first]--;
        }
        else if(que.size()>0)  { 
            if(que[que.begin()->first] == 1)
                que.erase(que.begin()->first);
            else 
                que[que.begin()->first]--;
        }
    }
 
    if(que.size() == 0)
        return {0, 0};
 
    return {(--que.end())->first, que.begin()->first};
}
 

 

 

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 (programmers.co.kr)