링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626

코드

1 sol - 실패

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 차례대로 추출하기 위해 우선순위 큐에 모두 삽입
        for (int s : scoville) {
            pq.add(s);
        }
        
        int answer = 1;
        while (pq.size() >= 2) {
            // 두 음식을 섞어서 새로운 음식을 만들어 삽입
            pq.add(pq.poll() + (pq.poll() * 2));
            // 가장 안 매운 음식이 K 이상이면 정답 리턴
            if (pq.peek() >= K)
                return answer;
            answer++;
        }
        
        return -1;
    }
}

실패의 원인을 되짚어보면, 모든 음식이 처음부터 K 이상이어서 섞을 필요가 없는 경우에도, 루프에 진입해 강제로 한 번 섞은 뒤 1을 반환하는 논리적 오류가 있었다.

2 sol

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        // 낮은 숫자가 우선순위인 큐 생성 (Min Heap)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 차례대로 추출하기 위해 우선순위 큐에 모두 삽입
        for (int s : scoville) {
            pq.offer(s);
        }
        
        int answer = 0;
        while (pq.peek() < K) {
            // 남은 음식이 1개인데도 K 미만이면 만들 수 없는 경우
            if (pq.size() == 1) {
                return -1;
            }
            
            // 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식 꺼내기
            int first = pq.poll();
            int second = pq.poll();
            
            // 섞은 음식의 스코빌 지수 계산
            int mixed = first + (second * 2);
            
            // 섞은 음식을 다시 큐에 삽입
            pq.offer(mixed);
            answer++;
            
        }
        
        return answer;
    }
}

참고자료

• LeetCode
• 자바 알고리즘 인터뷰