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

https://programmers.co.kr/learn/courses/30/lessons/42629

 

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42629
문제 설명

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.
dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한사항

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

입출력 예

stock	dates	supplies	k	result
4	[4,10,15]	[20,5,10]	30	2

 

풀이

처음에는 복잡하게 생각해서 문제가 엄청 어려웠었다.
고려해야 할 부분은 두개였다.
 1. 보급은 최대한 많이 받는게 좋다.
 2. 보급을 받는 날까지 공장이 돌아갈 수 있을까.
이 문제를 해결하기 위해 지나간 보급날들의 보급의 양을 기록해 두고, 재고가 떨어지면 보급을 받는 방법으로 했다.
(사실은 보급날 보급을 받아야 하지만, 약간 킵해뒀다가 고르는 느낌)
사실 아무 내림차순 정렬만 되는 자료구조면 상관 없으나 우선순위 큐를 사용하여 편하게 구현하였다.
시간복잡도는 날짜순으로 진행하므로, $O(N)$ 이다.
코드의 구성에서 질문글의 코드를 참고하였다.

 

코드

class Solution {
	PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Comparator.reverseOrder());
	
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = launchFactory(stock, dates, supplies, k);
        return answer;      
    }
    
    public int launchFactory(int stock, int[] dates, int[] supplies, int k) {
    	int supplied = 0;
    	int rest = k - stock; //가진거 빼고 버텨야 하는 날
        int days = 0;	//하루하루
        int supplyChance = 0;	//보급기회
        

        while(rest > 0){
        	//매일매일 1톤씩 소비
            days++;
            stock--;
            
            //만약 보급날 오면 -> 무조건 보급 받는게 아니라, 우선순위큐에 땡길 수 있는 양만큼 정렬해서 기록해두기.
            if(supplyChance < dates.length && days == dates[supplyChance]){            	
                heap.offer(supplies[supplyChance]);                               
                if(supplyChance >= dates.length)break;
                supplyChance++; 
            }
            
            //만약 재고가 다 떨어졌으면 -> 기록해둔 큐(보급 땡길수 있는 거)에서 가장 많이 빼올 수 있는거 빼기
            if(stock == 0){
                stock = heap.poll();
                rest = rest- stock; //날짜 다시 계산
                supplied++;
            }
        }
        
        return supplied;
    }
}

 

결과

테스트 1 〉 통과 (1.30ms, 50.2MB)
테스트 2 〉 통과 (1.51ms, 50.1MB)
테스트 3 〉 통과 (1.21ms, 52.2MB)
테스트 4 〉 통과 (1.68ms, 52.6MB)
테스트 5 〉 통과 (1.58ms, 49.8MB)
테스트 6 〉 통과 (1.52ms, 52.4MB)
테스트 7 〉 통과 (1.54ms, 52.6MB)
테스트 8 〉 통과 (1.43ms, 50.5MB)
테스트 9 〉 통과 (1.51ms, 50.6MB)
테스트 10 〉통과 (1.54ms, 52.5MB)
테스트 11 〉통과 (1.25ms, 50.1MB)
(효율성)
테스트 1 〉 통과 (4.59ms, 52.1MB)
테스트 2 〉 통과 (3.48ms, 53.9MB)
테스트 3 〉 통과 (10.17ms, 53.1MB)