[프로그래머스] 더 맵게

코드 힌트

1. PriorityQueue 사용하기
   • 우선순위 큐는 각 요소가 우선순위에 따라 정렬되어 큐에 저장됩니다. 이 문제에서 PriorityQueue를 사용하면 가장 작은 스코빌 지수를 효율적으로 가져올 수 있습니다. 일반 큐나 리스트를 사용할 경우, 효율성 테스트에서 시간 초과가 발생할 수 있습니다.
   • PriorityQueue는 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 구조입니다. 여기서 우선순위는 낮은 숫자일수록 높은 우선순위를 가집니다.
2. 섞은 음식들과 섞지 않은 음식들 모두 스코빌 지수(K)보다 높아야 합니다
   • 두 개의 가장 작은 스코빌 지수를 꺼내어 새로운 스코빌 지수를 만들어 우선순위 큐에 다시 추가합니다.
   • 이 과정을 반복하여 모든 음식이 K 이상의 스코빌 지수를 갖도록 만듭니다.
3. 만약 조건에 맞지 않는다면 -1을 반환해야 합니다
   • 우선순위 큐에 남은 음식이 하나인데 스코빌 지수가 K보다 낮으면 더 이상 섞을 수 없으므로 -1을 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int result = 0;
        // 스코빌 지수를 저장할 우선순위 큐 생성 (기본적으로 최소 힙)
        PriorityQueue<Integer> pqScov = new PriorityQueue<>();
        
        // 모든 스코빌 지수를 우선순위 큐에 추가
        for (int n : scoville) {
            pqScov.add(n);
        }
        
        // 우선순위 큐의 크기가 1보다 클 동안 반복
        while (pqScov.size() > 1) {
            // 가장 작은 스코빌 지수가 K 이상이면 현재 섞은 횟수를 반환
            if (pqScov.peek() >= K) 
                return result;
            
            // 가장 맵지 않은 음식 두 개를 꺼내어 섞음
            int leastHot = pqScov.poll();
            int secondLeastHot = pqScov.poll();
            
            // 섞은 새로운 음식의 스코빌 지수를 우선순위 큐에 추가
            pqScov.add(leastHot + secondLeastHot * 2);
            result++;
        }
        
        // 마지막 남은 음식이 K 이상인지 확인
        if (pqScov.peek() >= K)
            return result;
        
        // 조건에 맞는 경우가 없다면 -1 반환
        return -1;
    }
}