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

[프로그래머스] 고득점 Kit 힙 - 이중우선순위큐

 

< 문제 >

 

< 풀이 >

#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    int qSize=0;
    
    for(int i=0; i < operations.size(); i++)
    {
        if(operations[i][0] == 'I')
        {
            string number = "";            
            for(int n=1; n<operations[i].length(); n++)
            {
                if(operations[i][n] != ' ')
                    number += operations[i][n];
            }
            
            stringstream intNumber(number);
            int pushNum;
            intNumber >> pushNum;
            
            qSize++;
            answer.push_back(pushNum);
            sort(answer.begin(), answer.end());
        }
        else if(operations[i] == "D 1")
        {
            if(qSize <= 0)
                continue;
            answer.pop_back();
            qSize++;
        }
        else if(operations[i] == "D -1")
        {
            if(qSize <= 0)
                continue;
            
            answer.erase(answer.begin());
            qSize--;
        }
    }
    
    if (qSize <= 0 || answer.size() == 0)
        return { 0,0 };
    else
    {
        return {answer[answer.size()-1], answer[0]};
    }
}

 

< 해설 >

이중우선순위 큐라고 적혀있어서 우선순위 큐 2개를 가지고 풀이를 하려다가 코드도 길어지길래 그냥 벡터로 풀으니 너무나 쉬웠던 문제... (또 낚시문제임 ㄱ-)

이런문제는 데이터를 넣을때마다 sort를 해주는데 이 곳에서라도 시간초과가 나게 문제를 만들었으면 더 좋은 문제가 되지 않았을까 하는 생각이 든다.

 

푸는 방법은 answer벡터에 값을 넣어주고 넣어줄때마다 sort를 해준다. 그리고 D 1 , D -1 을 만날때마다 끝에있는값, 맨 앞의 값을 삭제해주기만 하면 된다. 최소값 삭제시점마다 벡터의 맨 앞의값을 삭제하는 것은 효율성이 떨어지는것이 아닌가요? 싶지만 테스트케이스들이 0.07ms 이상으로 끝나는것들이 없다...(이무슨..)

 

무지성벡터이용이 빛을발하는 문제