더 맵게

문제

문제의 시간 복잡도

n의 개수는 백만개 이하로 $O(n)$ 이하의 시간 복잡도를 사용 해야 된다고 생각을 했다.

큐의 시간복잡도를 살펴보면
삽입, 삭제 연산의 경우 $O(logN)$의 시간이 걸린다. 즉 heapify가 걸리는 시간이 $O(logN)$ 이라는 것이다.

여기서 큐를 말한 이유는 문제에서 사용하는 우선순위 큐는 힙을 이용해서 만들었기 때문이다.

풀이

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=0;i<scoville.size();i++)
    {
        q.push(scoville[i]);
    }
    
    while(q.size() > 1)
    {
        if(q.top() < K)
        {
            int a = q.top();
            q.pop();
            
            int b = q.top();
            q.pop();
            
            int c = a+(b*2);
            q.push(c);
            answer++;
        }
        
        else return answer;
        
    }
    
    if(q.top() < K) return -1;
    return answer;
}

우선순위큐를 이용하여 쉽게 문제를 풀 수 있었다.

여기서 하나 몰랐던 부분은 C++은 우선순위큐가 default로 최대힙으로 구현이 돼있다. 따라서 greater<int> 인수를 주어 최소힙으로 만들어 줄 수 있다.