[우선순위 큐, comparable] 프로그래머스 level2 라면공장 자바 풀이

프로그래머스 라면 공장 자바(java) 풀이

• Level 2
• 힙
• 라면 공장
  
  
  

문제 정리

1. 공장에서 하루에 밀가루 1톤씩 사용한다.
2. 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다.
3. 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다.
4. 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다.
5. 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라
6. stock: 현재 남아있는 밀가루 양
   dates[]: 밀가루 공급 일정
   supplies[]: 해당 시점에 공급 가능한 수량
   K: 원래 공장으로부터 공급받을 수 있는 시점
7. stock에 있는 밀가루는 오늘(0일)부터 사용된다.
8. k일 째에는 밀가루가 충분히 공급되므로 k-1일에 사용할 수량까지만 확보하면 된다.
9. dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급된다.
   9일째에 바닥나더라도 10일째에 공급받으면 10일째에 운영할 수 있다.
10. dates의 각 원소는 k 이하이다.
11. 밀가루가 바닥나는 경우는 주어지지 않는다.
    
    
    

힙, 우선순위 큐

stock 즉, 재고를 수명으로 생각합니다. stock이 K 이상이 되면 k일을 버틸 수 있다는 의미이므로 그 때까지 보급품을 받으면 됩니다.

1. 현재 stock보다 이전 날짜들의 공급 양을 모두 우선순위 큐에 넣습니다.
   왜냐하면 재고가 떨어지기 전에(수명이 다 되기전에) 공급을 받아야 살기 때문입니다.
2. 그리고 우선순위 큐에서 공급 양이 가장 많은 것만을 받습니다.
3. 받은 횟수를 증가시킵니다.
4. 이를 stock이 k보다 작은 동안 반복하여 공급을 받습니다.
   
   
   

Comparable 구현

우선수위 큐에 넣을때 숫자를 넣으면 기본 오름차순으로 정렬이 됩니다.
이를 내림차순으로 정렬하기 위해서 class를 정의하고 comparable을 구현하였습니다.

1. Flour class를 생성합니다.
2. Comparable을 상속받습니다.
3. 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;
    }
}