[42626번] 더 맵게

힙(Heap)

 

✔️ 문제 설명

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

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

✔️ 입출력 예

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

 

✔️ 제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

✔️ 코드 구상

Heap 문제인데다가 효율성 검사도 있다! 무조건 Heap을 사용해보도록 하자.

루트 노드를 항상 최소값으로 하는 MinHeap을 사용해야 할거 같다. 자바는 PriorityQueue가 그걸 구현해준다.

Queue에 스코빌 지수들을 입력하면 자동으로 최소힙정렬이 되기 때문에

poll()로 꺼내와서 K랑 크기비교해주고 작으면 계산식에 따라 계산해서 다시 queue에 넣고 카운트하고 크면 넘어간다.

-1이 반환되는 예외를 처리하기 위해 간단하게 '섞은 회수 + 섞지 않아도 K보다 큰 개수 = 전체 개수' 식으로 판별한다.

 

✔️ 코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scovilles, int K) {
        int answer = 0;
        int count = 0;
        long n = (long) K;

        PriorityQueue<Object> minHeap = new PriorityQueue<>();

        for(int scoville : scovilles) {
            minHeap.add(scoville);
        }

        while(!minHeap.isEmpty()) {
            try {
                int node = (int) minHeap.poll();

                if(node < n) {
                    minHeap.add(node + ((int) minHeap.poll() * 2));
                    answer++;
                } else {
                    count++;
                }
            } catch (Exception e) {}
        }

        return answer + count == scovilles.length ? answer : -1;
    }
}

 

📄 원문

https://programmers.co.kr/learn/courses/30/lessons/42626