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

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

코딩테스트 연습 - 라면공장 | 프로그래머스

코드

package Programmers.Level2;

import java.util.Collections;
import java.util.PriorityQueue;

public class NoodleFactory {

	public static void main(String[] args) {

		int stock = 3;
		int[] dates = { 4,10,15 } ;
		int[] supplies = { 20,5,10 } ;
		int k = 1;

		int answer = solution( stock, dates, supplies, k);

		System.out.println(answer);

	}

	public static int solution(int stock, int[] dates, int[] supplies, int k) {

		int answer = 0;

		int day = stock; // 최초 0 이되는 날짜다.

		int index = 0 ; // add한 supplie를 기록한다.

		PriorityQueue<Integer> amounts = new PriorityQueue<Integer>(Collections.reverseOrder());

		// supplie를 할 수 있는 경우.
		while ( day < k ) {
			// supplie를 add 할 수 있는 경우의 수를 구하기.
			while( index < dates.length && dates[index] <= day) {
				// 사용한 밀가루 보다 공급일이 작거나 같은경우
				amounts.add(supplies[index]);
				index++;
			}
            
			day+= amounts.poll();
			answer++;
		}
		return answer ;
	}

}

제출 결과

후기

입출력 예

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

 

입출력 예 설명

• 현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
• 4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
• 따라서 총 2회의 밀가루를 공급받으면 됩니다.

정리하면, 위 예시에서 K일까지 버티기 위해서는 4일 차 때 20톤을 받고, 15일 차 때 10톤을 받으면 2번만 지원받고 버틸 수 있다.  ( 10일 차 때 5톤을 안 받아도 남은 밀가루가 있기 때문에 버티다가 15일 차 때 받는 게 더 효율적이다. )

 

간단하게 해결 할 수 있는 핵심은 priorityQueue를 사용하는 것이다.

 

- K까지 버티기위해서 밀가루를 받을 때 가장 효과적으로 받으면 됨.

 

- 어떻게?

- 밀가루 양으로 버틸 수 있는 날짜(이하 day변수로 표현)를 구함.

- 사용한 밀가루의 양 = 날짜

 

- 최초 stock으로 주어진 양은 공급받지 않고 무조건 다 쓸 수 있음

- 그럼 초기의 day = stock이 됨.

 

- day가 K보다 커질때까지 공급받으면 됨.

- 공급받는 밀가루 양은 받을 수 있는 거중에서 가장 큰 거를 받는 것이 최적의 선택임.

- day <= supplies[index] 조건에 맞는 대상을 priorityQueue에 모두 add 해주고

- 하나씩 poll 하면 가장 큰 거부터 처리되도록 구현됨.

 

이런 문제를 보면 핵심을 빠르게 찾을 수 있도록 더 많이 풀어봐야 할 것 같다..