Programmers <더 맵게>

---

Level 2

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
  
  

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

작성 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int newSco = -1;   // Queue의 값이 하나일 경우 대비
    priority_queue<int, vector<int>, greater<int>> q;   // min heap
    
    for(int i=0; i<scoville.size(); i++)
        q.push(scoville[i]);
    
    while(q.top() < K) {
        newSco = q.top();
        q.pop();
        if(q.empty())
            return -1;
        newSco += (q.top() * 2);
        q.pop();   // 가장 작은 값, 두번째로 작은 값을 꺼내 새로운 값 계산
        q.push(newSco);   // Min Heap에 새로 push
        answer++;  // 계산 횟수 count
    }
    return answer;
    
}

📌

• 값들을 가장 큰 것부터(작은 것부터) 처리해야 할 경우 우선순위 큐(priority queue)를 사용할 수 있다
• 모든 값들이 x보다 클 때(작을 때)를 알기 위해서는 우선순위 큐의 top의 값을 확인하면 알 수 있다
  ex) 우선순위 큐(min heap) q의 top값이 10이라면 모든 값들이 10보다 작거나 같은 것이고, 우선순위 큐(max heap)의 값이 10이라면 모든 값들이 10보다 크거나 같은 것이다