더 맵게

🔒 문제

💭 생각의 흐름

음식을 섞다 -> 최소 맵기 2개의 음식을 섞어 1개의 음식이 된다. (음식 갯수 -1)
모든 음식을 K 이상으로 만들 수 없다 -> 음식 갯수가 N개 일 때 N-1 번 섞어서 K보다 작으면 -1 return

"가장 싱거운 (맵지 않은 음식) 2개가 매 Loop 마다 필요하다 -> 최소 힙을 사용하자. 최소힙 베이스의 우선 순위 큐에서 2개씩 빼면 곧 O(Log N) 연산으로 맵지 않은 음식을 섞어 넣을 수 있다.

⚠️ c++의 priority queue 초기화시 기본은 최대 힙으로 생성된다. 따라서 힙 생성 기준을 바꿔줄 operator 오버라이딩이 필요하다. 또, 배열 최대 길이가 100만까지 길기 때문에 초기화부터 배열을 인자로 넘기는 것이 효율에 좋다.
(∵ vector는 자체적으로 원소 갯수가 capacity를 넘길 때마다 자체적으로 O(N)의 복사를 수행한다.)

// min heap 생성을 위한 비교 operator overriding
struct CompareValue {
    bool operator()(const int& previousValue, const int& nextValue) const {
        return previousValue > nextValue;
    }
};
    // make min heap based Priority Queue
    priority_queue<int, vector<int>, CompareValue> priorityQueue(scoville.begin(), scoville.end());

사실 C++에선 오름차순/내림차순을 위한 기본 함수 오브젝트를 지원한다.

(1) 앞 원소가 뒤 원소보다 '>' 큰 경우 swap (자리 바꿈) => 오름차순 // min heap 생성에 사용될 수 있음.
(2) sort 인자로 넘기면 내림차순이 됨. (앞 원소가 뒤 원소보다 '>' 큰 경우 true)

🔑 풀이 (C++)

#include <vector>
#include <queue>

using namespace std;

struct CompareValue {
    bool operator()(const int& previousValue, const int& nextValue) const {
        return previousValue > nextValue;
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;

    // make min heap based Priority Queue
    priority_queue<int, vector<int>, CompareValue> priorityQueue(scoville.begin(), scoville.end());

    while (priorityQueue.size() != 1 && priorityQueue.top() < K) {
        const int minSpicy = priorityQueue.top();
        priorityQueue.pop();
        const int secondMinSpicy = priorityQueue.top();
        priorityQueue.pop();
        
        priorityQueue.emplace(minSpicy + secondMinSpicy * 2);
        answer++;
    }

    return (priorityQueue.top() < K) ? -1 : answer;
}

📊 결과

🔗 참고