level 2 - 더 맵게(100/100)

• 문제 설명 : 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

• 제한 사항

• scoville의 길이는 1 이상 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

• 입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

• 내가 만든 코드

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    priority_queue<int,vector<int>,greater<int>> q;
    int answer = 0;
    int min = 0;
    int min1,min2;
    for(int i = 0; i<scoville.size(); i++){
        q.push(scoville[i]);
    }
    
    while(q.top() < K){
        if(q.size()==1){
            return -1;
        }
        min1 = q.top();
        q.pop();
        min2 = q.top();
        q.pop();
        min =  min1 + min2*2;
        q.push(min);
        answer++;
    }
    return answer;
}

1. 우선순위 큐(Heap)을 사용하는 문제이고, min heap을 사용해야 sort과정이 생략되어 실행시간이 줄어들기 때문에 min heap을 배워서 사용했다.
2. priority_queue<int,vector<int>,greater<int>> q; 라고 선언을 해주면 min heap을 사용할 수 있다. (less<int>는 max heap이다.)
3. 원하는 스코빌 지수보다 min값이 작으면 반복
4. queue에 저장된 값이 1개지만 아직도 반복문에 들어와있다면 불가능한 경우이므로 -1를 return했다.
5. 2개 이상이라면 가장 작은 값과 두 번째로 작은 값을 각각 변수에 집어 넣고 pop해준 후, 주어진 공식에 대입하여 새로운 스코빌 지수를 만든다.
6. 그 후 우선순위 큐에 만들어진 스코빌 지수를 push한 후 몇 번 섞었는지에 대한 변수 answer를 증가시킨다.

• 코드 채점 결과

• 군대를 다녀오기 전, 트리를 배웠었지만 이 문제를 풀 때 우선순위 큐라는 것을 완전히 잊고 있었던지라 sort하는데 수행시간을 매우 많이 잡아먹었다.
• 인터넷에 Heap을 검색하고 C++에서 우선순위 큐(max heap, min heap)를 사용하는 방법에 대해 익힌 후 코드를 작성해보니 효율성 테스트까지 빠르게 통과할 수 있었다.