[프로그래머스](Heap) 더 맵게 (C++)

더 맵게 (Level 2)

문제

전체 문제 보기

코딩테스트 연습 - 더 맵게

접근법

문제에서 요구하는 것은 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해서 섞어야 하는 최소 횟수이다. 음식을 섞을 때는 다음과 같은 방법으로 섞게 된다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

두 개의 음식을 섞을 때마다 스코빌 지수는 증가하기 때문에 원소들을 순차적으로 정렬을 하더라도 순서가 뒤바뀌는 일이 발생할 수 있다. 그래서 배열을 사용할 경우 섞은 음식의 삽입 위치를 찾기 위해서는 최악의 경우 \(O(n)\)의 시간 복잡도를 가진다. 반면 우선순위 큐(Heap)를 이용할 경우 \(O(log n)\) 시간 복잡도 삽입 위치를 찾을 수 있다. 때문에 모든 음식을 섞어야 하는 최악의 경우에 배열을 사용하게 될 경우 \(O(n^2)\)의 시간 복잡도를 가지게 되고 우선순위 큐를 사용할 경우 \(O(n log n)\)의 시간 복잡도를 가지기 때문에 이 문제는 우선순위 큐를 활용하는 것이 더욱 효율적인 해결책이 된다.

구현

다음과 같은 순서로 해결 할 수 있다.

• 모든 원소의 스코빌 지수를 우선순위 큐에 오름차순으로 담는다. (가장 낮은 값이 우선순위를 가지도록)
• 스코빌 지수가 가장 낮은 음식이 K 보다 작다면 아래의 섞기 작업을 반복한다.
  • 큐에 남아있는 음식이 하나 뿐이라면 원하는 맵기 값을 만들 수 없기에 answer에 -1을 대입 후 반복문을 종료한다.
  • 그렇지 않다면, 섞기 공식에 따라 두 음식을 섞어준다.
• 최종 결과를 반환한다.

#include <vector>
#include <queue>
#include <functional>

using namespace std;

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

    // 우선순위 큐 오름차순으로 사용
    priority_queue<int, vector<int>, greater<int>> pq;

    // 스코빌 지수를 우선순위 큐에 삽입
    for(int s : scoville)
        pq.push(s);

    // 우선순위큐에서 첫 번째 요소는 스코빌 지수가 가장 낮은 음식.
    // 스코빌 지수가 가장 낮은 음식이 K보다 작다면 계속 섞기 작업 반복
    while(pq.top() < K){       
        int firstFood = pq.top();
        pq.pop();

        // 우선순위 큐가 비었다면 원하는 맵기값 만들 수 없기에 answer에 -1 대입 후 반복문 종료
        if(pq.empty())
        {
            answer = -1;
            break;
        }

        int secondFood = pq.top();
        pq.pop();

        // 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 섞는다.
        pq.push(firstFood + secondFood * 2);      
        answer++;
    }

    return answer;
}