[42626] 더 맵게

✔ 더 맵게

[프로그래머스 42626]

문제 분석하기

가장 낮은 두 개의 음식을 골라야 하므로 힙을 구현한 우선순위 큐를 사용하여 음식들을 정렬하는 방식으로 문제에 접근

우선순위 큐에 객체를 추가 인자 없이 생성하면 Min Heap으로 동작하게 됨

// Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 그 외에 다른 객체에 따라 정렬할 경우 Comparable<>의 compareTo() 구현

 

손으로 풀어보기

1. 우선순위 큐에 음식을 저장
2. 가장 스코빌 지수가 낮은 두 개의 음식을 골라 새로운 음식을 만들고 저장
3. 모든 음식이 스코빌 지수 K 이상일 경우 섞어야 하는 최소 횟수 리턴
   • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 리턴

슈도코드 작성하기

scoville(음식의 스코빌 지수)
K(원하는 스코빌 지수)
minHeap(음식의 스코빌 지수를 담은 우선순위 큐)
minHeap에 scoville 저장
answer(최소 횟수)
while(minHeap.peek < K) {
    if(모든 음식을 스코빌 지수 K 이상으로 만들 수 없고 음식이 하나일 때)
        -1 리턴
    새로운 음식을 만들고 저장
    최소 횟수 증가
}
answer 리턴

코드 구현하기

/**
 * 42626) 더_맵게
 */
public class K001_42626 {
    // scoville(음식의 스코빌 지수)
    // K(원하는 스코빌 지수)
    public int solution(int[] scoville, int K) {
        // minHeap(음식의 스코빌 지수를 담은 우선순위 큐)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // minHeap에 scoville 저장
        for (int food : scoville) {
            minHeap.add(food);
        }
        // answer(최소 횟수)
        int answer = 0;
        while (minHeap.peek() < K) {
            // 모든 음식을 스코빌 지수 K 이상으로 만들 수 없고 음식이 하나일 때
            if (minHeap.size() == 1)
                // -1 리턴
                return -1;
            // 새로운 음식을 만들고 저장
            minHeap.add(minHeap.poll() + minHeap.poll() * 2);
            // 최소 횟수 증가
            answer++;
        }
        // answer 리턴
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_42626 solution = new K001_42626();

        int[] scoville = { 1, 2, 3, 9, 10, 12 };
        int K = 7;

        int result = solution.solution(scoville, K);

        System.out.println(result);
    }
}