chaerryos-blog

[프로그래머스/C++] 더 맵게

6 min read

문제

문제 설명

매운 것을 좋아하는 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회입니다.

풀이

처음 제출한 코드 (61.3 / 100.0)

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
    // 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
    // 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 구하기
    
    // point: 음식을 섞을 때마다 스코빌 지수를 기준으로 새롭게 정렬이 되어야한다 -> 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq; // min heap
    
    // K보다 스코빌 지수가 작은 것만 신경쓰면 된다.
    for (auto s : scoville) {
        if (s < K) {
            pq.push(s);
        }
    }
    
    while (!pq.empty()) {
        int s1 = pq.top();
        pq.pop();
        int s2 = pq.top();
        pq.pop();
        int sn = s1 + (s2 * 2);
        answer++;
        if (sn < K) {
            pq.push(sn);
        }
    }
    
    return answer;
}

문제점

  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 해당 조건을 포함하지 않았다.
  • 이 코드로는 pq에 원소가 하나만 존재할 경우 에러가 발생한다.

정답 풀이

  • 기존: pq에 스코빌 지수가 k 이하인 원소들만 넣은 뒤에, pq가 비어있을 경우 종료하는 방식
  • 변경: pq에 모든 원소를 넣고, top의 원소가 k 이상일 경우에 종료
#include <string>
#include <vector>
#include <queue>
#include <functional>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
    // 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.
    // 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 구하기
    
    // point: 음식을 섞을 때마다 스코빌 지수를 기준으로 새롭게 정렬이 되어야한다 -> 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq; // min heap
    
    for (auto s : scoville) {
        pq.push(s);
    }
    
    while (true) {
        int s1 = pq.top();
        pq.pop();
        if (s1 >= K) {
            break; // 종료 조건
        }
        if (pq.empty()) {
            return -1; // 다 섞었는데도 종료 불가라면 -1리턴
        }
        
        int s2 = pq.top();
        pq.pop();
        int sn = s1 + (s2 * 2);
        answer++;
        
        pq.push(sn);
    }
    
    return answer;
}

Graph View