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

https://programmers.co.kr/learn/courses/30/lessons/42629

코딩테스트 연습 - 라면공장

풀이 방법

하루에 밀가루를 1톤씩 사용하므로, 밀가루 재고가 amount일 때 현재 날짜가 amount 보다 크거나 같으면 밀가루 재고가 부족하다. 따라서 이 경우에는 그 전에 밀가루를 미리 구매해야 한다.

 

이때, 밀가루 구매 횟수를 최소화하기 위해서는 한번에 최대한 많이 구매할 수 있는 날에 구매해야 한다. 따라서 우선순위 큐를 두어서 한번에 구매할 수 있는 최대 수량을 저장해나간다. 그리고 현재 날짜까지 사용할 수 있는 충분한 양의 밀가루를 구매한다.

while(amount <= dates[i]){
    amount += pq.top();
    pq.pop();
    answer++;
    if(amount >= k) return answer;
}

 

한편, 밀가루 재고가 딱 떨어지는 날에 구매해야만 하는 경우가 있을 수 있다. 이 경우에는 우선순위 큐가 비어있기 때문에 먼저 우선순위 큐에 추가하도록 한다. 그리고 그 날의 수량을 -1로 업데이트하여 우선순위 큐에 한번 더 추가하더라도 문제 없도록 한다.

if(amount == dates[i]){
    pq.push(supplies[i]);
    supplies[i] = -1;
}

while(amount <= dates[i]){ ... }

pq.push(supplies[i]);

 

전체 코드는 여기서 확인할 수 있다.