문제 설명
라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요. dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
제한사항
입출력 예
입출력 예 설명
|
재고가 다 떨어지는 날을 기준으로 그날까지 조달할 수 있던 최대 갯수의 원료를 선택해 받는 과정을 계속 반복하는 문제입니다. 일반 리스트에 넣어두고 최대값을 찾아도 풀 수 있긴 하지만 최대 힙트리를 사용하면 최대값을 구하는 시간이 거의 들지 않습니다. 최대 힙트리는 항상 부모 노드보다 자식노드의 값이 작은 이진 트리이며, 완전 정렬된 상태가 아닙니다.
힙트리 구조는 자바에서 우선순위 큐(PriorityQueue) 클래스로 제공하고 있어 편하게 사용할 수 있습니다. 기본적인 개념은 아래 링크를 참조하시면 됩니다.
[▸C언어/알고리즘 및 자료구조] - 정렬알고리즘_힙 정렬 [6/8]
원료를 한 번 받으면 남은 재고갯수와 동일한 날짜에 남는 재고가 없어집니다. 이 날을 기준으로 받을 수 있었던 최대 원료량을 카운트하면 됩니다.
package pojoPrj;
import java.util.PriorityQueue;
class Solution {
public static void main(String[] args) {
public int solution(int stock, int[] dates, int[] supplies, int k) {
int answer = 0;
int oringDay = stock; // 재고가 오링나는 날 (= 재고 갯수)
// 최대 힙트리로 변경
PriorityQueue<Integer> p = new PriorityQueue<>((o1, o2) -> {
if (o1 < o2) {
return 1;
}
return -1;
});
for (int i = 0; i < dates.length; i++) {
// 오링나는 날이 K와 같거나 높아지면 상관없음
if (oringDay >= k) {
return answer;
}
// 오링나는 날보다 작거나 같은 경우 큐에 담아줌
if (dates[i] <= oringDay) {
p.add(supplies[i]);
}
// 오링데이 변동 전 임시 저장
int preOringDay = oringDay;
// 오링나는 날짜보다 뒷 날짜가 나오면 그 전 날에서 받을 수 있는 가장 많은 공급량을 선택
if (dates[i] >= oringDay) {
answer++;
oringDay += p.remove();
}
// 이전 날짜에서 공급량 선택 후 현재 날짜의 공급량 추가
if (dates[i] > preOringDay) {
p.add(supplies[i]);
}
}
// 끝까지 갔는데 오링나는 날이 아직 k보다 이전이라면 가장 큰 순서대로 큐에서 공급량 선택
while (oringDay < k) {
answer++;
oringDay += p.remove();
}
return answer;
}
}
'▸알고리즘 문제 풀이' 카테고리의 다른 글
프로그래머스_힙(Heap)_이중우선순위큐 (JAVA) (0) | 2020.04.28 |
---|---|
프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA) (4) | 2020.04.27 |
프로그래머스_힙(Heap)_더맵게 (JAVA) (0) | 2020.04.23 |
프로그래머스_스택/큐_주식가격 (JAVA) (1) | 2020.04.23 |
프로그래머스_스택/큐_쇠막대기 (JAVA) (0) | 2020.04.23 |
댓글