[프로그래머스] 라면공장 (Java)

프로그래머스 라면공장

문제풀이

이 문제에 핵심은 공급받을 수 있을 때 공급받는 것이 아니라 필요할 때 가장 큰 공급량을 공급받는 것이다. 따라서 최대 힙을 이용해서 공급을 받아야하는 시점에 공급받을 수 있는 가장 큰 공급을 받는다.

• 공급받을 수 있는 날이 되면 우선순위 큐에 공급량을 넣는다.
• 밀가루가 다 떨어진(-1) 날에 우선순위 큐에서 가장 큰 공급량을 공급 받는다.
• 우선순위 큐를 오름차순으로 사용하려면 Collections.reverseOrder()을 사용한다.

구현코드

import java.util.*;

class Solution {
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int supplyIdx = 0;
        
        for(int i = 0 ; i < k ; ++i){
            if(supplyIdx < dates.length && i == dates[supplyIdx]){
                pq.offer(supplies[supplyIdx++]);
            }
            
            stock--;
            
            if(stock == -1) {
                stock += pq.poll();
                answer++;
            }
        }
        
        return answer;
    }
}