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

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

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

( 제한사항을 보면 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일째에는 공장을 운영할 수 있습니다.
밀가루가 바닥나는 경우는 주어지지 않습니다.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42629

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

 

핵심 

1 우선순위 큐
stock이 바닥날때, 바닥나는 날짜 이전에서 최대 공급량을 선택한다.
왜냐하면, 최소 횟수로 공급 받으려면 매 번 공급받을 때마다 최대로 공급받아야 한다. 그래야 공급받은 stock이 바닥날 때까지 최대한 많은 공급 가능 경우를 고려할 수 있다. 그리고 거기서 다시 최대 공급량을 선택.. 
 

2 stock : 작업 후 남은 양 vs 작업 전 남은 양

Date	0	1	2	3	4
작업 후 남은 양	3	2	1	0
작업 전 남은 양	4	3	2	1	0

 

공급은 작업 전에 제공된다.

date 4에서 작업 전 stock이 0이어도 작업 전에만 공급받으면 괜찮기 때문에 date 4도 최대 공급날짜로 고려해야한다. 

그래서, stock을 '작업 전 남은 양'로 정의한다. ( stock이 0일 때, 최대 가능 공급양을 선택 ) 

 

3 예제가 다양하지도 않고 적다. 
  1 '왜 틀렸지', '왜 해당 로직을 선택했지' 

  2 여러 케이스 고려

 

 

구조

2 가지를 기준으로 만들 수 있다. 

 

1 k?날짜 기준 

for ( 모든 날짜 date )

    if( 오늘이 공급날짜 )

        우선순위 큐에 공급량 저장 

    if( stock == 0)

       stock += pq.poll();

       cnt++;

    stock--;

 

2 공급날짜 기준 

데드라인 = stock

for ( 모든 공급날짜 )

    if ( 공급 날짜 > 데드라인 ) 공급 날짜 <= 데드라인인 경우, 데드라인이 바뀌어야 하는 경우가 없나? 확실히 하기

        데드라인 += pq.poll()

        cnt++

    pq.add(공급량)

 

while( 데드라인 < k )

    데드라인 += pq.poll()

 

 

공급 날짜를 기준으로 할 경우 생각이 더 어렵다. 예제에도 걸리지 않고.. 

데드라인이 모든 dates를 넘지만, k보다 작은 경우를 고려하지 않아 틀렸다. 

 

날짜 기준으로 푸는 것이 더 깔끔하고 다른 예외도 자동 처리되지만, k가 1억을 넘어갈 경우, 공급날짜를 기준으로 풀어야 한다. 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

 

k날짜 기준 

import java.util.*;
class Solution {
	public int solution(int stock, int[] dates, int[] supplies, int k) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
       
		int cnt = 0, dIndex = 0;
		for(int date = 0 ; date < k ; date++) {
			if(dIndex < dates.length && dates[dIndex] == date) {
				pq.add(-supplies[dIndex]);
				dIndex++;
			}
			if(stock == 0) {
				stock += -pq.poll();
				cnt++;
			}
			stock--;
		}
		return cnt;
	}
}

 

공급날짜 기준 

import java.util.*;
class Solution {
	public int solution(int stock, int[] dates, int[] supplies, int k) {
		int deadLine = stock, cnt = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		for(int i = 0 ; i < dates.length; i++) {
			if(deadLine < dates[i]) {
				deadLine += -pq.poll();
				cnt++;
			}
			pq.add(-supplies[i]);
		}
		while(deadLine < k) {
			deadLine += -pq.poll();
			cnt++;
		}
		return cnt;
	}
}