Table of contents

프로그래머스 더 맵게

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

각 요소가 음식의 스코빌 지수를 의미하는 배열 scoville과 원하는 스코빌 지수 K가 주어졌을 때, 모든 음식의 스코빌 지수가 K 이상인 경우가 될 때까지 음식을 섞는 회수를 구하는 문제이다.

가장 작은 값과, 그 다음 작은 값을 이용하기 때문에 최소힙을 이용하면 쉽게 풀 수 있다. 자바에서는 우선순위큐 PriorityQueue를 사용한다. 우선순위가 높은 요소가 가장 먼저 출력되는 자료구조이다. Integer는 Comparable이며 디폴트로 작은 값이 높은 우선순위를 갖는다.

private int scoville(int[] scoville, int K) {
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i : scoville) queue.add(i);

    int count = 0;
    while(queue.size() > 1 && queue.peek() < K) {
        int weakHot = queue.poll();
        int secondWeakHot = queue.poll();

        int mixHot = weakHot + (secondWeakHot * 2);
        queue.add(mixHot);
        count++;
    }

    if (queue.size() <= 1 && queue.peek() < K) return -1;

    return count;
}
  1. scoville 배열의 모든 요소를 우선순위큐에 넣는다.
    1. 두개의 요소를 꺼내서 mix한 뒤 다시 큐에 넣는다.
    2. 섞은 횟수를 증가시킨다.
  2. 만약, 우선순위큐에 요소가 하나 남은 상태에서 해당 요소가 K보다 작은 경우 -1을 반환한다.
    1. 큐에 요소가 하나라면 섞을 수 있는 모든 요소를 다 섞었다는 의미이다.
  3. 그렇지 않다면 모든 요소가 K 이상의 맵기를 가졌다는 의미이므로 성공, 섞은 횟수를 반환한다.