[Programmers] Level2 : 더 맵게

Question

---

Solution

• 스코빌 지수에 충족되지 않은 ‘i’음식이 있다면 i 바로 다음(‘i+1’)으로 매운 음식과 섞어야 한다.
• 위 사항에서 알 수 있는 것은 다음과 같다.
  1. 지수가 가장 낮은 음식 부터 시작한다.
  2. ‘i’의 지수가 낮다면 ‘i+1’의 지수가 충족되라도 섞어줘야 한다.
  3. ‘i’의 지수가 낮은데 ‘i’ 음식 단 한개만 있다면 모두 k 지수로 만들 수 없는 경우로 -1을 return 한다.
• 숫자들이 계속해서 정렬되어야하고, 두 개의 값을 섞을때 공간에서 각각 빼내고 새로운 값을 다시 집어넣어야한다.
  이에 맞는 자료구조는 set과 priority_queue가 있지만 set의 경우는 중복되는 음식의 지수가 올 수 없기 때문에 제외된다.

---

Cord

#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>> res; // 오름차순으로 정렬

    // queue에 주어진 초기 값 담기 
    for (int i : scoville) { res.push(i); }

    while (res.size() > 1)
    {
        if (res.top() >= K) { break; }

        // 섞을 두개의 음식 빼내기
        int min = res.top();
        res.pop();

        int second = res.top();
        res.pop();

        // 합쳐진 새로운 음식 넣기
        res.push(min + second * 2);
        ++answer;
    }

    // 가장 작은 스코빌 지수가 k보다 작을 때
    if (res.top() < K) { answer = -1; }

    return answer;
}

---

Result