[힙] 더 맵게

|| 문제설명 ||

1. 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어한다.

2. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.

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

3. Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

4. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성하라.

• scoville : Leo가 가진 음식의 스코빌 지수를 담은 배열
• K : 원하는 스코빌 지수

_ scoville의 길이 : 2 이상 1,000,000 이하
_ K : 0 이상 1,000,000,000 이하
_ scoville의 원소: 0 이상 1,000,000 이하
_ 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return

---

|| 문제해결방법 ||

- 우선순위큐 <int> 형의 변수를 선언하여 scoville의 모든 원소 push
- 정렬된 상태의 원소들을 앞에서부터 차례로 만들기
- 새롭게 만든 스코빌 지수는 변수에 추가해 주고 계속 반복해 나감
- 섞을 때마다 answer을 증가시켜줌

---

|| 코드 ||

[2020.08.08] 실패

#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>> pq;
    for(auto i = scoville.begin(); i != scoville.end(); i++) {
        pq.push(*i);
    }
    for(int i=0; i<pq.size()+answer; i++) {
        if(pq.top() < K) {
            int tmp = pq.top();
            pq.pop();
            pq.push(tmp + pq.top() * 2);
            pq.pop();
            answer++;
        }
    }
    return answer;
}

• 문제 이해부족 : "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다."의 조건 누락

[2020.08.08] 성공

- 스코빌 지수를 만족하지 못하는 원소가 하나만 남았을 때 return -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>> pq;
    for(auto i = scoville.begin(); i != scoville.end(); i++) {
        pq.push(*i);
    }
    for(int i=0; i<pq.size()+answer; i++) {
        if(pq.top() < K) {
            if(i == pq.size()+answer - 1) {
                return -1;
            }
            int tmp = pq.top();
            pq.pop();
            pq.push(tmp + pq.top() * 2);
            pq.pop();
            answer++;
        }
    }
    return answer;
}

---

[2021.01.23]

- "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 
	= 남아있는 요소가 K보다 작고 하나만 남았을 때

#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>> list;
    
    for(int i=0; i<scoville.size(); i++) list.push(scoville[i]);
    
    for(int top = list.top(); top < K; top = list.top()) {
        if(list.size() == 1) return -1;
        
        list.pop();
        list.push(top + list.top() * 2);
        list.pop();
        answer++;
    }
    return answer;
}

공간복잡도가 매우 떨어졌다.

그저 과거와 지금은 달랐던 것 이전 코드를 다시 돌려보니 똑같은 결과가 나왔다.