더 맵게 (프로그래머스)

힙의 특성을 이용하면 원활하게 풀 수 있는 문제이다.

 

'스코빌 지수가 가장 낮은 음식'에 주목하자. 이는 최소 힙을 이용한다면 쉽게 가져올 수 있다. 힙에 대해 더 자세하게 알고 싶다면 다음 링크를 참고하길 바란다.

https://lipcoder.tistory.com/entry/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue?category=804356

우선순위 큐 (Priority Queue)

힙은 STL에서 std::priority_queue를 지원하기 때문에 이것을 사용하면 매우 편하게 힙을 사용할 수 있다.

 

과정을 차례대로 적어보면 다음과 같다.

1. 최소 힙 h를 만든다.

2. 모든 음식 정보를 h에 담는다.

3. h에서 A, B 음식을 꺼낸다. (최소 힙이기 때문에 차례대로 꺼내면 스코빌 지수가 가장 낮은 음식을 꺼낸다.)

4. A + (B * 2)를 한 음식을 h에 다시 넣는다. 이때 섞을 횟수를 하나 올려준다.

5. h의 가장 위의 음식(스코빌 지수가 가장 낮은 음식)의 스코빌 지수가 k와 같거나 클 때까지 3 ~ 4 작업을 반복한다.

   (만약 h가 비어 있다면 스코빌 지수를 k로 올릴 수 없는 상황이므로 -1를 반환한다.)

코드는 다음과 같다.

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    // 최소 힙 선언
    priority_queue<int, vector<int>, greater<int>> q;
    // 최소 힙에 모든 음식 스코빌 지수를 넣는다.
    for(const auto iter : scoville) q.push(iter);
    while(true)
    {
        // 가장 낮은 스코빌 음식을 꺼낸다.
        int val1 = q.top(); q.pop();
        // 만약 K보다 크거나 같으면 조건을 만족하므로 루프종료
        if(val1 >= K) break;
        // 만약 힙이 비어있다면 더이상 섞을 수 없으므로 -1 반환
        else if(q.empty())
        {
            answer = -1;
            break;
        }
        // 2번째로 낮은 스코빌 음식을 꺼낸다.
        int val2 = q.top(); q.pop();
        // 섞고 힙에 넣는다.
        q.push(val1 + val2 * 2);
        // 섞은 횟수를 증가해준다.
        ++answer;
    }
    return answer;
}