더 맵게

문제 설명

매운 것을 좋아하는 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 <set>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    set<int> answerSet(scoville.begin(), scoville.end());

    while ((*answerSet.begin()) < K && answerSet.size() > 1)
    {
        int first = (*answerSet.erase(answerSet.begin()));
        int second = (*answerSet.erase(answerSet.begin()));

        int defresult = first + second * 2;
        answerSet.insert(defresult);
        answer++;
    }

    if ((*answerSet.begin()) >= K)
        return answer;
    return -1;
}

실패.

 

동작사항 자체는 옳으나,

중복된 값을 무시하는 Set을 고려하지 않고 사용하여, 중복된 값이 기입될 수 있다는걸 생각하지 못했다.

 

일부 실패한 사례

 

---

두번째 시도

#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>> minHeap(scoville.begin(), scoville.end());

    while (minHeap.top() < K && minHeap.size() > 1) {
        int first = minHeap.top(); minHeap.pop();
        int second = minHeap.top(); minHeap.pop();

        int mixedScoville = first + second * 2;
        minHeap.push(mixedScoville);
        answer++;
    }

    if (minHeap.top() >= K)
        return answer;
    return -1;
}

성공

 

우선순위 queue를 사용하여, 데이터를 역순으로 정렬.

 

역순 정렬 데이터를 set을 사용한것 과 같은 방식으로 데이터를 사용했다.

 

중복값을 무시하지 않음으로 데이터 사용이 성립하였다.