[프로그래머스] - 더 맵게

문제 링크

문제 풀이

최소 힙 문제

구상

과정을 보고 최소힙을 사용하면 쉽게 풀 수 있다고 생각했습니다.

저는 자바로 풀어서 PriorityQueue 클래스를 이용했습니다.

먼저 매개변수로 주어진 scoville의 값들을 PriorityQueue에 모두 넣고

root의 값이 K가 넘을 때까지(혹은 다른 예외가 있을 경우) 음식을 섞고 따로 count를 1씩 더했습니다.

문제를 보고 규칙을 정해서 어떤 상황일 때 음식을 섞을지 고민을 했습니다.

1. 최소 힙의 크기는 2 이상
   • 음식을 섞을 때 두개로 섞기 때문에 그 미만이면 NPE가 일어날 수 있다.
2. root의 크기는 K보다 작아야한다.
   • 힙의 root가 K보다 크면 섞는 과정이 필요 없습니다.

그리고 어떻게 섞어도 음식들이 K를 안넘을 경우를 생각해 봤습니다.

• 예) scoville=[0, 0, 0], K = 1

이 경우에는 음식을 섞는 과정을 모두 거치고 최소힙에 존재하는 값들중 하나라도 K보다 작으면 -1을 리턴하도록 구성했습니다.

코드

package pro_42626;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    public static int solution(int[] scoville, int K) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        Arrays.stream(scoville).forEach(priorityQueue::add);
        int answer = 0;

        while (priorityQueue.size() >= 2 && priorityQueue.peek() < K) {
            int topFood = priorityQueue.poll();
            int nextFood = priorityQueue.poll();

            priorityQueue.add(topFood + nextFood * 2);
            answer++;
        }

        answer = (priorityQueue.stream().filter(x -> x < K).findFirst().isEmpty()) ? answer : -1;

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{0, 0, 0}, 1));;
    }
}