라면공장
문제: https://programmers.co.kr/learn/courses/30/lessons/42629?language=java
1. 문제설명
라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.
dates[i]에는 i번째 공급 가능일이 들어있으며, amounts[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
2. 나의코드
- 밀가루 수량(supplies)을 담을 PriorityQueue를 만든다.(Descending Order)
- 전체 재고가 st이라 할 때, 밀가루 공장은 st만큼 공장이 가동 될 수 있으으로, st가 k보다 커지기 전 까지만 while 문을 돌린다.
- 재고가 떨어질 때쯤, 재고가 떨어지기 전 날짜에 해당하는 공급(supplies) 중에서 가장 큰 공급량을 선택한다.(PrioityQueue 에서 poll() call! )
- st에 poll()한 공급량을 더해주고 index 값을 갱신하여, 이전에 확인했던 공급(supplies)를 중복하여 큐에 넣거나, 확인하지 않도록 한다. 위의 과정을 반복한다.
import java.util.*;
class Solution {
public int solution(int stock, int[] dates, int[] supplies, int k) {
int answer = 0;
int index = 0;
int index2 = 0;
int st = stock;
PriorityQueue <Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
while(st < k){
for(int i = index ; i < dates.length;i++){
if(dates[i] <= st){
pq.offer(supplies[i]);
index2 = i;
}
}
index = index2+1;
st += pq.poll();
answer++;
}
return answer;
}
}
3. 다른사람 코드
- index를 밖으로 빼서 사용하는 방법도 있다.
int answer = 0;
int day = stock;
int index = 0;
while(day < k) {
while(index < dates.length && dates[index] <= day) {
queue.add(supplies[index]);
index++;
}
answer++;
day += queue.poll();
}
