문제

Programmers, 더 맵게

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 스코빌 지수를 K 이상으로 만들어야 한다. 이는 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 합하여 만들 수 있다. 매번 섞으며 스코빌 지수가 K가 이상인지 확인하기 위해 힙 자료구조인 우선순위 큐를 사용한다. 최소 힙을 사용하면 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 효율적으로 찾을 수 있다.
• 두 음식을 섞기 전에 이미 스코빌 지수를 충족한 경우를 놓치지 말자!

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

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

Java

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; ++i)
            pq.add(scoville[i]);
        if (pq.peek() >= K)
            return 0;
        int answer = 0;
        while (pq.size() > 1) {
            int before = pq.poll();
            pq.add(before + pq.poll() * 2);
            ++answer;
            if (pq.peek() >= K)
                return answer;
        }
        return -1;
    }
}