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

 

문제

소스코드

#include <string>
#include <vector>
#include<set>
using namespace std;
 
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    set<int,std::greater<int>> set;
    for (auto& oper : operations) {
        //Set에 삽입
        if (oper[0] == 'I') {
            oper.erase(0, 2);
            set.emplace(atoi(oper.c_str()));
        }
 
        //Set의 최대값 혹은 최솟갑 삭제
        else if (oper[0] == 'D' && set.empty()==false) {
            //최솟값 삭제
            if (oper[2] == '-') {
                //가장 뒤에있는 값이 가장 작은값
                auto iter = --set.end();
                set.erase(iter);
            }
            //최대값 삭제
            else {
                set.erase(set.begin());
            }
        }
    }
 
    if (set.size() == 0) {
        answer.emplace_back(0);
        answer.emplace_back(0);
    }
    else {
        answer.emplace_back(*(set.begin()));
        answer.emplace_back(*(--set.end()));
    }
    return answer;
}
 
 
int main() {
 
    //vector<string> operations = { "I 16","D 1"};
    vector<string> operations = { "I 7","I 5","I - 5","D - 1" };
    solution(operations);
 
}
 

 

후기

이 문제를 해결하기 위한 키워드는 Set이다.

 

이 문제는 주어진 명령어에 따른 Queue에 남은 최댓값과 최솟값을 출력하는 문제이다. 이 문제를 해결하기 위해서 가장 먼저 생각난 자료구조가 우선순위 큐(Priority Queue)였다. 하지만 우선순위 큐 컨테이너의 문제점은 Top()의 값만 확인할 수 있고 나머지 값들은 순환을 해야 하기 때문에 비효율적이다.

 

그다음 생각한 것이 Deque 자료형과 Sort를 사용해서 앞과 뒤에서 최댓값을 빠르게 꺼내는 것이다. 이 방법은 매번 삽입을 진행할 때마다 Sort를 진행하기 때문에 매우 비효율이다. 특히 대부분 정렬이 진행된 자료구조에 quick Sort는 최악의 복잡도를 보여준다.  

 

여기서 생각해본것이 Set 자료형이다.  Set은 자료구조는 기본적으로 정렬을 시도하며 begin(), end()를 통해 최댓값과 최솟값을 파악할 수 있기 때문에 Set을 이용했으며 통과할 수 있었다. 만약 중복 문제가 생긴다면 multiSet도 고려해볼 수 있다고 본다.

 

출처 및 레퍼런스

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42628