개발기록장

더 맵게

5 min read

문제 링크
난이도 : Lv. 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 합니다.
입출력 예
scovilleKreturn
[1, 2, 3, 9, 10, 12]72
입출력 예 설명

  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회입니다.

문제 분석

스코빌 지수는 오름차순으로 정렬되어 있으면 편함.

주기적으로 실행되야 하는 것은 두 가지

  1. 앞에서 두 요소가 뽑힘
  2. 요소를 추가함. (이때 오름차순 유지하면서 되야함) ⇒ 요소를 넣을 때 마다 자동으로 정렬되는 힙 사용 그 중에서도 오름차순이어야 하니까, Min Heap을 사용함

작성한 코드

#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>> q(scoville.begin(), scoville.end());
    
    while(true) {
        if(q.size() == 0) return -1;
        if(q.size() == 1 && q.top() < K) return -1;
        if(q.top() >= K) return answer;
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        q.push(a + (b * 2));
        answer++;
    }
    
    return answer;
}

c++에서 우선순위 큐가 힙으로 구현되어있기 때문에 사용했음.

우수 코드 분석

#include <vector>
#include <queue>
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());
 
    while(pq.top()<K) {
        if(pq.size()==1) return answer = -1;
        needHot=pq.top(); pq.pop();
        pq.push(needHot+pq.top()*2);
        pq.pop(); answer++;
    }
 
    return answer;
}

pq의 사이즈가 0이 될 일은 없다는 점을 인식하지 못했다… (시작 사이즈가 최소 1이라)

그래프 뷰