[프로그래머스][C++] 이중우선순위큐

이중우선순위큐

문제 링크

이중우선순위큐

분석

vector<string> operations의 원소는 큐가 수행할 연산을 나타내며, 명령어 데이터 형식으로 주어집니다.

• "I 숫자": 큐에 해당 숫자를 삽입합니다.
• "D 1": 큐에서 최댓값을 삭제합니다.
• "D -1": 큐에서 최솟값을 삭제합니다.

최댓값혹은 최솟값이 둘 이상인 경우 하나만 삭제합니다.

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

모든 연산이 끝난 후 큐에 남아있는 값 중 최댓값과 최솟값을 반환해야합니다.
만약 큐가 비어있는 경우 [0, 0]을 반환합니다.

풀이

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    // 자동으로 정렬되며, 중복 허용되는 자료구조
    // priority_queue를 대체한다.
    multiset<int> ms;
    
    // 연산 배열 순회
    for(auto& oper : operations)
    {
        // 삽입 연산일 경우
        if (oper[0] == 'I')
        {
            // 숫자부분을 추출하여 정수로 변환하고 저장
            int num = stoi(oper.substr(2));
            ms.insert(num);
        }
        // multiset이 비어있지 않고, 삭제 연산인 경우
        else if (!ms.empty())
        {
            if (oper[2] == '1')
            {
                // 최댓값 삭제
                auto it = prev(ms.end());
                ms.erase(it);
            }
            else
            {
                // 최솟값 삭제
                ms.erase(ms.begin());
            }
        }
    }
    
    if (ms.empty())
    {
        return {0, 0};
    }
    
    // multiset이 비어있지 않는 경우 최댓값과 최솟값을 저장한다.
    answer.push_back(*prev(ms.end()));
    answer.push_back(*ms.begin());
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \ log \ m)$입니다.

• 연산 배열을 순회하는 반복문 $O(n)$
• multiset자료형의 삽입 속도 $O(log m)$
  • m은 저장된 원소 수
• $O(n \ log \ m)$

공간 복잡도는 $O(n)$입니다.

• priority_queue를 대체하는 multiset<int> ms $O(n)$

테스트 성능

테스트 1 〉 통과 (0.02ms, 3.63MB)
테스트 2 〉 통과 (0.02ms, 3.67MB)
테스트 3 〉 통과 (0.02ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.02ms, 4.21MB)
테스트 7 〉 통과 (10.05ms, 10.9MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.02ms, 4.21MB)