더 맵게 | 리버

Level2

프로그래머스📅 2025-07-04

우선순위 큐힙그리디

문제 설명

매운 것을 좋아하는 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 합니다.

입출력 예

입력

scoville = [1, 2, 3, 9, 10, 12], K = 7

출력

설명

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

풀이 접근법

시간복잡도 : O(N log N)

공간복잡도 : O(N)

사용 알고리즘 :

우선순위 큐(Min Heap)

핵심 포인트 :

매번 가장 작은 두 값을 찾아야 하므로 Min Heap 사용
섞은 후 새로운 값을 다시 힙에 삽입하여 재정렬
모든 음식이 K 이상이 될 때까지 반복
음식이 2개 미만이면서 여전히 K 미만인 경우 -1 반환

경계값/반례 :

모든 음식을 다 섞어도 K에 도달할 수 없는 경우: -1 반환
처음부터 모든 음식이 K 이상인 경우: 0 반환
음식이 1개만 있는 경우: K 이상이면 0, 미만이면 -1

핵심 아이디어

이 문제는 섞을 때마다 재정렬이 필요합니다. 우선순위 큐를 사용하면 자동 재정렬이 되므로 효율적으로 해결할 수 있습니다.

생각 과정

우선순위 큐로 정렬 및 섞은 후 재정렬

PriorityQueue<Integer> que = new PriorityQueue<>();
for (int i = 0; i < scoville.length; i++) {
  que.add(scoville[i]);
}

while (que.size() >= 2) {
  int first = que.poll();
  int second = que.poll();
  
  int newNum = first + (second * 2);
  que.add(newNum);
}

왜 필요? 이 문제는 섞을 때마다 재정렬이 필요하다. ⇒ 우선순위 큐를 사용하면 자동 재정렬
섞은 음식의 스코빌 지수가 기존의 정렬을 깰 수 있기 때문

예외 처리

if (scoville.length < 2) {
  return -1;
}

if (que.peek() >= K) {
  return 0;
}

if (first == 0 && second == 0) {
  return -1;
}

if (que.peek() < K) {
  return -1;
}

음식이 2개 미만인 경우
처음부터 조건을 만족하는 경우
더 이상 섞을 수 없는데 조건 미달인 경우

최종 제출 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        if (scoville.length < 2) {
          return -1;
        }

        PriorityQueue<Integer> que = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
          que.add(scoville[i]);
        }

        if (que.peek() >= K) {
          return 0;
        }

        int count = 0;
        while (que.size() >= 2) {
          if (que.peek() >= K) {
            break;
          }
          int first = que.poll();

          int second = que.poll();
          if (first == 0 && second == 0) {
            return -1;
          }

          int newNum = first + (second * 2);
          que.add(newNum);
          count++;
        }
        
        if (que.peek() < K) {
            return -1;
        }

        return count;
    }
}