프로그래머스 라면 공장 자바(java) 풀이
문제 정리
- 공장에서 하루에 밀가루 1톤씩 사용한다.
- 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다.
- 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다.
- 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다.
- 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라
- stock: 현재 남아있는 밀가루 양
dates[]: 밀가루 공급 일정
supplies[]: 해당 시점에 공급 가능한 수량
K: 원래 공장으로부터 공급받을 수 있는 시점
- stock에 있는 밀가루는 오늘(0일)부터 사용된다.
- k일 째에는 밀가루가 충분히 공급되므로 k-1일에 사용할 수량까지만 확보하면 된다.
- dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급된다.
9일째에 바닥나더라도 10일째에 공급받으면 10일째에 운영할 수 있다.
- dates의 각 원소는 k 이하이다.
- 밀가루가 바닥나는 경우는 주어지지 않는다.
힙, 우선순위 큐
stock 즉, 재고를 수명으로 생각합니다. stock이 K 이상이 되면 k일을 버틸 수 있다는 의미이므로 그 때까지 보급품을 받으면 됩니다.
- 현재 stock보다 이전 날짜들의 공급 양을 모두 우선순위 큐에 넣습니다.
왜냐하면 재고가 떨어지기 전에(수명이 다 되기전에) 공급을 받아야 살기 때문입니다.
- 그리고 우선순위 큐에서 공급 양이 가장 많은 것만을 받습니다.
- 받은 횟수를 증가시킵니다.
- 이를 stock이 k보다 작은 동안 반복하여 공급을 받습니다.
Comparable 구현
우선수위 큐에 넣을때 숫자를 넣으면 기본 오름차순으로 정렬이 됩니다.
이를 내림차순으로 정렬하기 위해서 class를 정의하고 comparable을 구현하였습니다.
- Flour class를 생성합니다.
- Comparable을 상속받습니다.
- compareTo 함수를 구현합니다.(내림차순)
this의 값보다 인자로 받은 값이 더 클때: 1 return
this의 값보다 인자로 받은 값이 더 작을때: -1 return
같을때: 0 return
프로그래머스 라면공장 자바 코드
import java.util.*;
class Flour implements Comparable<Flour>{
int amount;
Flour(int amount){
this.amount = amount;
}
// 내림차순
@Override
public int compareTo(Flour a){
if(this.amount > a.amount)
return -1;
else if(this.amount < a.amount)
return 1;
else
return 0;
}
}
class Solution {
public static void main(String[] args) {
int stock = 4;
int[] dates = {4,10,15};
int[] supplies = {20,5,10};
int k = 30;
System.out.println(solution(stock, dates, supplies, k));
}
public static int solution(int stock, int[] dates, int[] supplies, int k) {
int ans = 0;
PriorityQueue<Flour> pq = new PriorityQueue<>();
int idx = 0;
// stock: 수명
// stock이 k이상이 되면 남은 공급으로 k일을 버틸 수 있음을 의미
while(stock < k){
for(int i=idx, len=dates.length; i<len; i++){
// 수명이 끝나기 전에 받을 수 있는 공급 넣어놓기
if(stock >= dates[i]){
pq.offer(new Flour(supplies[i]));
idx = i+1; // 중복으로 queue에 넣는것 방지
}
}
// 받을 수 있는 것 중에 공급 많이 주는것만 받기
stock += pq.poll().amount;
ans++;
}
return ans;
}
}