알고리즘 풀이: [프로그래머스] 라면공장

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

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

문제 설명

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 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일째에는 공장을 운영할 수 있습니다.

 

밀가루가 바닥나는 경우는 주어지지 않습니다.

 

입출력 예

stock	dates	supplies	k	return
4	[4, 10, 15]	[20, 5, 10]	30	2
4	[1, 2, 3, 4]	[1, 1, 1, 1]	6	2

 

입출력 예 설명

현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.

 

4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.

 

따라서 총 2회의 밀가루를 공급받으면 됩니다.

---

문제 풀이

부모의 값이 자식들의 값보다 크거나 같은 최대 힙(max heap)을 사용해서 문제를 해결합니다.

 

 

초기화 단계

 

초기화 단계

하루에 재고가 1 소진되므로 k 일까지 버티기 위한 목표 재고량은 k 입니다. stock으로 초기화된 현재 재고량은 때에 따른 공급량을 더해주면서 목표 재고량 k를 만듭니다. 최종적으로 공급량을 더해주는 횟수를 구합니다.

 

현재 재고량과 목표 재고량을 비교하여서 버틸 수 있는 경우와 버틸 수 없는 경우를 구분합니다. 버틸 수 없는 경우는 곧 공급량이 필요한 경우입니다.

 

 

그렇다면 어떠한 날짜의 공급량을 받는 것이 최선의 선택일까요?

 

어떠한 날짜의 공급량을 받을 지에 대한 선택 기준은 두 가지입니다.

 

1. 현재 재고량으로 버틸 수 있는 날짜 안에 공급량이 들어와야 한다. 

2. 기왕 받을 거 한 번에 많은 공급량을 받는 것이 좋다.

 

따라서 현재 재고량에 더해줄 공급량은 현재 재고량으로 버틸 수 있는 날짜를 dates 에서 찾고, 해당 날짜의 공급량 중 최대 공급량을 선택합니다.

 

 

마지막으로 공급량이 현재 재고량에 더해지면 공급 횟수는 1 증가합니다.

 

이러한 과정을 반복하면서 현재 재고량이 목표 재고량보다 크거나 같으면 더 이상 공급을 받을 필요 없이 현재 공급 횟수를 반환하여 문제를 해결합니다.

 

 

첫 번째 공급 단계

첫 번째 공급량(20)을 재고량에 더해줍니다.

초기화된 현재 재고량은 4로 목표 재고량 30에 미치지 못합니다. 따라서 최선의 공급량을 찾아서 더해줍니다.

 

앞서 말한 최선의 공급량 선택 기준에 따르면 현재 재고량으로 버틸 수 있는 일 수는 4일입니다. dates가 4일을 포함하여 그 이전에 들어오는 공급량 중 최대 공급량을 선택합니다. 예시에 따르면 4일에 공급량 20 말고는 다른 공급량이 없습니다. 따라서 20을 현재 재고량에 더합니다. 

 

공급 횟수는 1 증가합니다.

 

 

두 번째 공급 단계

두 번째 공급량(10)을 재고량에 더해줍니다.

첫 번째 공급량을 찾은 것처럼 두 번째 공급량도 찾습니다. 현재 재고량으로는 24일까지 버틸 수 있으므로 10일과 15일에 들어오는 공급량 5와 10 중에서 최선의 공급량을 찾습니다. 10이 가장 큰 공급량이므로 현재 재고량에 더합니다.

 

공급 횟수는 1 증가합니다.

 

 

2번의 공급을 통해 목표 재고량에 도달합니다.

2번의 공급으로 목표 재고량 30 도달

두 번의 공급으로 현재 재고량은 34가 됩니다. 따라서 목표 재고량보다 크므로 현재 재고량으로 원하는 기일까지 버틸 수 있습니다. 따라서 공급 횟수가 2를 반환합니다.

 

 

파이썬에서 최대 힙은 어떻게 구하나요?

 

힙을 구현한 파이썬 내장 라이브러리 heapq 는 기본적으로 최소 힙(min heap) 입니다. 따라서 최대 힙을 위해서는 원소에 (-1)을 곱해서 힙에 저장하면 최대 힙처럼 사용할 수 있습니다. 해당 원소를 pop 하여서 사용할 때 (-1)을 곱해서 원래의 원소의 값으로 복원합니다. 

 

 

소스 코드

메인 솔루션 함수

import heapq


def solution(stock, dates, supplies, k):
    # 최대 힙을 위한 힙
    heap = list()

    # 인덱스: 현재 재고량으로 버틸 수 있는 일수를 가리킨다
    idx = 0

    # 공급 횟수 카운터
    counter = 0

    # 현재 재고량으로 목표치를 버틸 수 없는 경우
    while stock < k:
        # 현재 재고량으로 버틸 수 있는 일수의 공급량을 모두 힙에 저장
        # 최대 힙으로 구현해야하므로 -1 이 곱해진다
        while idx < len(dates) and dates[idx] <= stock:
            heapq.heappush(heap, -supplies[idx])
            idx += 1

        # -1이 곱해져서 원래의 공급량으로 복원
        supply = -1 * heapq.heappop(heap)

        # 재고량에 공급량 반영
        stock += supply

        # 공급 횟수 증가
        counter += 1

    return counter


if __name__ == '__main__':
    assert solution(4, [4, 10, 15], [20, 5, 10], 30) == 2
    assert solution(4, [1, 2, 3, 4], [1, 1, 1, 1], 6) == 2

프로그래머스

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EB%9D%BC%EB%A9%B4%EA%B3%B5%EC%9E%A5.py

dhsong95/-PRACTICE-Programmers-Algorithm