[알고리즘] 프로그래머스 라면공장 -heap(힙)-

 

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

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

 

오랜만에 알고리즘을 풀어봤습니다. 

Level2 에 heap 문제입니다. 

자바에서는 힙을 우선순위큐로 구현합니다. (PriorityQueue)

 

* 밀가루가 0개일때 지급받을 밀가루가 없는 경우는 없다고 가정합니다.

[첫날부터 목표날인 k까지 반복문을 돌립니다.]

1. 지급날짜인 경우 내림차순인 우선순위 큐에 밀가루를 추가합니다.

2. 밀가루 재고가 0인 경우 큐에서 가장 많은 밀가루를 가져오고 answer가 +1 됩니다.

3. 하루가 지날때마다 밀가루는 한개씩 줄어듭니다.

 

풀이와 설명(주석)은 다음과 같습니다.

[Java]

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

class Solution {
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder()); // 밀가루 많은 순으로 정렬
        int dateIndex = 0;

        // 끝나는날짜(k) 까지 반복
        for (int i = 0; i < k; i++) {
            // 지급할게 남아있고 밀가루 주는 날짜인 경우 밀가루 공급
            if (dateIndex < dates.length && dates[dateIndex] == i) {
                queue.offer(supplies[dateIndex]);
                dateIndex++;
            }
            // 남은 밀가루 0일 경우 공급받기
            if (stock == 0) {
                stock += queue.poll();
                answer++;
            }
            // 하루마다 밀가루 -1
            stock--;
        }
        return answer;
    }
}

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%9D%BC%EB%A9%B4%EA%B3%B5%EC%9E%A5%20-heap(%ED%9E%99)-

mtjin/algorithm_practice