찬우의 이것저것 Chanwoo's blog

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

2020-04-17

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 result
4 [4,10,15] [20,5,10] 30 2

문제 카테고리가 heap이어서 heap을 써야하나보다라는 생각을했지 카테고리가 주어지지 않았으면

접근방법을 헤메지 않았을까..생각이 드는 문제였다.

도대체 카테고리가 왜 heap이야? 라는 생각을 무척 오래하다가 date를 배제하고 가장 빨리 끝내는 방법을 먼저 생각해보고 나서 date를 고려하니 어느부분에 heap이 필요한지 문제가 다시 보였다.

처음에는 supplies 를 전부 heap에 넣고 제일 큰걸 빼는 방식으로 생각했는데

날짜를 같이 생각하려니 머리가 복잡했다.

  • 남아있는 밀가루 stock이 필요한 밀가루양(하루에1톤) k보다 크거나 같아질때까지 while
  • 보급받는날 dates를 체크해서 현재 stock보다 작으면 현재 보급을 받을수 있으니 heap에 추가
  • 다음 loop에서 heap에 중복된 값을 추가하지 않기위해 index를 증가 (start = i + 1)
  • heap에 들어있는 보급 가능한 밀가루중 가장 많은 양을 선택(heappop)
  • 보급을 받으면 count += 1
import heapq


def solution(stock, dates, supplies, k):
    q = []
    supplied_count = 0
    start = 0

    while stock < k:
        for i in range(start, len(dates)):
            if dates[i] <= stock:
                heapq.heappush(q, (-supplies[i], supplies[i]))
                start = i + 1
            else:
                break

        stock += heapq.heappop(q)[1]
        supplied_count += 1

    return supplied_count


if __name__ == '__main__':
    stock, dates, supplies, k = 4, [4, 10, 15], [20, 5, 10], 30
    # stock, dates, supplies, k = 3, [2, 4, 10, 15], [11, 100, 5, 10], 35
    print(solution(stock, dates, supplies, k))

Related Posts