프로그래머스 - 더 맵게 (JAVA)

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

프로그래머스

 

접근 방식) 우선순위 큐 (최소힙) 사용

1) 모든 음식의 스코빌 지수를 우선순위 큐에 넣는다.

    그럼 우선순위 큐 첫번째 원소에는 최솟값이 위치하게 된다.

2) 우선순위 큐의 첫번째 원소가 K이상이 될 때까지 반복한다.

    - 원소가 1개만 있는데 K보다 작으면 -1 반환

    - 아니면, 큐에서 poll 해서 연산하고 다시 add해준다.

    - while() 문 반복한 횟수가 정답이 되므로, 돌 때마다 answer를 증가시켜준다.

 

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
              
        // 우선순위 큐(최소힙) 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : scoville) {
            pq.add(s);
        }
        
        //우선순위 큐(최소힙)에 넣고, 맨 앞의 수가 K 이상 될 때까지 반복한다.  
        int answer = 0;
        while (pq.peek() < K) {
            if (pq.size() == 1) return -1;
            
            int first = pq.poll();
            int second = pq.poll();
            pq.add(first + (second * 2));    
            answer++;
        }
        return answer;
    }
}