[Programmers/Level 2/Java] 라면공장

Programmers(프로그래머스) 라면공장

코딩테스트 연습 - 라면공장

문제 설명

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하라.

예)
stock = 4
dates = [4, 10 ,15]
supplies = [20, 5, 10]
k = 30
-> result: 2

풀이

처음에는 날짜를 하나씩 세면서 다음 공급일까지 stock이 충분히 남아있는지, 아니면 공급을 받아야 하는지로 접근을 했었는데, 이는 탐욕법으로 최소한의 방법을 알아내기에는 적합하지 않은 방법이었다.

최소한의 공급으로 K번째 날까지 버틴다는 건, 수량이 가장 많은 날에 공급을 받았다는 말과 비슷하다. 다만, 0번째 날부터 K번째 날까지 중 가장 많은 수량을 공급 받은 것이 아니라, 0번째 날부터 stock이 다 떨어진 현재 시점까지 중에서 가장 많은 수량을 공급받은 것으로 생각하면 된다.
즉, 밀가루를 언제 공급받을 것인지를 공급 받을 수 있는 날이 아니라, stock이 다 떨어진 시점에서 이전 공급 날 중에서 가장 많은 공급량을 선택하면 된다. 이미 지나간 날이지만, 그 당시에 공급받은 것으로 생각하면 된다.

문제의 분류가 Heap이지만, 나는 PriorityQueue로 풀었다.
언제든 가장 큰 값을 구할 수 있다면 어떤 자료구조를 사용하든 상관 없다.

다만, 전날 밀가루를 모두 소진했어도 다음 날 새벽에 공급을 받을 수 있으므로 연산 순서에 유의하면 좋을 것 같다.

import java.util.*;

class Solution {
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        int day = 0, index = 0;
        PriorityQueue<Integer> queueSupplies = new PriorityQueue<>(Collections.reverseOrder());
        
        while(day < k)
        {
            if(stock == 0)
            {
                stock += queueSupplies.poll();
                answer ++;
            }
            
            day ++;
            stock--;
            
            if(index < dates.length && dates[index] == day)
            {
                queueSupplies.offer(supplies[index]);
                index++;
            }
        }
        return answer;
    }
}