[Programmers] 라면공장 문제 풀이

# 프로그래머스 라면공장

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

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

문제에 대한 설명이 길어서 조금 복잡해 보인다. 이런 유형의 문제는 문제를 계속 읽어보고 예시에 설명된 과정을 그려보면 좋은 것 같다. 공급 가능일자가 되면 반드시 supplies[i]에 있는 밀가루만큼 공급받아야 한다는 의미가 아니라 이후에 언제든 해당 밀가루만큼 공급받을 수 있다는 의미로 이해해야 한다.

public int solution(int stock, int[] dates, int[] supplies, int k) {
    int answer = 0;
    Queue<Integer> supplyQueue = new PriorityQueue<>(Comparator.reverseOrder());
    int lastAddedDateIndex = 0;

    for (int i = 0; i < k; i++) {
        for (int j = lastAddedDateIndex; j < dates.length; j++) {
            if (i == dates[j]) {
                supplyQueue.add(supplies[j]);
                lastAddedDateIndex = j;
            }
        }
        if (stock == 0) {
            stock = supplyQueue.poll();
            answer++;
        }
        stock--;

    }

    return answer;
}

우선 효율성을 고려하지 않고 풀어봤다. 이 코드는 문제에 나온 과정을 그대로 코드로 옮긴 것이다. 오늘(0일) 부터 k - 1 일까지 남은 밀가루를 줄여나간다. dates에는 해외 공장으로부터 수입 가능한 날짜가 들어있으므로, 해당 날짜가 된다면 해당 날짜에 수입 가능한 수량을 큐에 넣는다. 최소한의 횟수로 밀가루를 공급받기 위해서는 가장 큰 수량부터 공급받아야 하기 때문에, 큐의 요소는 내림차순으로 정렬된다. 이 코드는 정확성 테스트는 통과하지만, 효율성 테스트는 모두 실패한다.

# 입출력 예

오늘(0일 차) 부터 밀가루를 사용하기 시작한다. 위의 예시를 살펴보자.

• 0일 차
  • 작업 시작: stock = 3
• 1일 차
  • 작업 시작: stock = 2
• 2일 차
  • 작업 시작: stock = 1
• 3일 차
  • 작업 시작: stock = 0
• 4일 차
  • 공급 일정 검사
    • dates[0] = 4, supplies[0] = 20
    • 공급 큐: [20]
  • 작업 시작 전
    • 남은 밀가루가 0이므로 공급
    • 공급 큐: [ ], stock = 20
  • 작업 시작: stock = 19
• 10일 차
  • 공급 일정 검사
    • dates[1] = 10, supplies[1] = 5
    • 공급 큐: [5]
  • 작업 시작: stock = 13
• 15일 차
  • 공급 일정 검사
    • dates[2] = 15, supplies[2] = 10
    • 공급 큐: [10, 5]
  • 작업 시작: stock = 8
• 24일 차
  • 작업 시작 전
    • 남은 밀가루가 0이므로 공급
    • 공급 큐: [5], stock = 10
  • 작업 시작: stock = 9
• 29일 차 (k - 1)
  • 작업 시작: stock = 4

4일 차, 24일 차에 각각 한 번씩 공급을 받는다.

이제 효율성을 통과시킬 방법을 찾아보자. 공급일자를 찾는 부분은 제외시킬 수 없다. 그렇다면 O(k)를 줄여야 한다는 이야기가 된다. k가 100,000 이하이며, dates의 길이(n)가 20,000 이하이기 때문에 복잡도가 O(kn) 이면 안되고 O(nlogk) 정도가 되어야 하는 것 같다.

public int solution(int stock, int[] dates, int[] supplies, int k) {
    int answer = 0;
    Queue<Integer> supplyQueue = new PriorityQueue<>(Comparator.reverseOrder());
    int lastAddedDateIndex = 0;
    int dateCanRunFactory = stock;

    while (dateCanRunFactory < k) {
        while (lastAddedDateIndex < dates.length && dates[lastAddedDateIndex] <= dateCanRunFactory) {
            supplyQueue.add(supplies[lastAddedDateIndex]);
            lastAddedDateIndex++;
        }

        dateCanRunFactory += supplyQueue.poll();
        answer++;
    }

    return answer;
}

위의 코드는 (day < k) 조건으로 인해, 공급이 필요한 날짜 만큼만 진행된다.

29일차까지 필요한 밀가루 수는 29개이다. 앞서 살펴본 것과 같이 3일 차에 밀가루를 모두 사용하여, 4일 차 오전에는 밀가루를 공급받아야 한다. 4일 차 오전에 20개를 공급받고 작업을 시작하여 19개의 밀가루가 남는다면, 23일 차까지 문제없이 공장을 돌릴 수 있게 된다. 다시 23일 차가 되면 밀가루를 모두 사용하게 되고, 24일 차 오전에 10개를 공급받는다. 마찬가지로 24일 작업을 시작하고 9개의 밀가루가 남는다면, 33일 차 까지 문제없이 공장을 돌릴 수 있게 되므로 day(34)가 k(30)보다 커지면서 종료된다.