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

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

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

---

    간단한 Heap 구조를 사용하는 Priority Queue를 사용하는 문제이다. 종료 조건은 PQ에서 두 숫자를 추출할 때 첫 번째로 뽑은 수가 K보다 크다면 그동안의 반복 횟수를 답으로 하고 그렇지 않고 뽑은 원소가 PQ의 마지막 원소라면 답은 -1 이 된다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

priority_queue <int,vector<int>,greater<int>> pq;
int solution(vector<int> scoville, int K) {
    int answer = -1,ep=0;
    int s1,s2;
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    }
    while(!pq.empty()){
        s1 = pq.top(); pq.pop();
        if(s1 >= K) {
            answer = ep;
            break;
        }
        else if(pq.empty())break;
        s2 = pq.top(); pq.pop();
        pq.push(s1 + s2 * 2);
        ep++;
    }
    return answer;
}

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = -1;
        int s1,s2,ep=0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<scoville.length;i++){
            pq.add(scoville[i]);
        }
        while(!pq.isEmpty()){
            s1 = pq.poll();
            if(s1 >= K) {
                answer = ep;
                break;
            }
            else if(pq.isEmpty())break;
            s2 = pq.poll();
            pq.add(s1 + s2 * 2);
            ep++;
    }
        return answer;
    }
}

---

    자바에서 PQ를 사용하는 것은 처음이었다. 원소를 추가하려면 .add() 혹은 .offer()를 사용하고 삭제하려면 .remove() 혹은 .poll()을 활용한다. 이때 remove()는 값을 삭제하고 만약 원소가 없다면 에러를 반환한다. poll의 경우 첫 번째 원소를 반환도 하면서 삭제도 하고 원소가 없다면 null을 반환한다. C++ 에서 top()과 front()를 같이 쓰는 것이라 굉장히 편하다. 원소가 비어있는지 확인 하는것은 .isEmpty()로 확인할 수 있다.