[프로그래머스][heap] 라면공장 python (200725)

1. 문제설명 

1) 

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

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

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

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

 

2) 제한사항

 

• 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일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

 

 

3) 입출력예시와 설명 

 

 

stock     //     dates   //  supplies //   k   //  result

 

4

[4,10,15]

[20,5,10]

30

2

 

현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다.

따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.

 

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

 

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

 

 

2. 풀이 

(사실 힙 이라고 안써놨으면 힙으로 풀어야 한다는 생각 1도 못했을듯)

 

핵심 : 1) 밀가루가 떨어지기 직전 (버티고 있는 상황에서) , 공급량이 가장 큰 날에 수입 받아야함

            (그래야 한번 더 다시 수입 받을 필요없이, 최소한의 횟수로 밀가루 공급받으니까 (문제에 설명해뒀음))

         2)하지만 중간에 비는 날이 있으면 안된다 다 떨어져버리기 전에 수입이 되어있어야 하는 상황!! 

 

적용 :  1) 리스트에서 가장 큰 수를 뽑아낸다 !  --> 최대 힙 사용. 

          2) 공급 가능한 날짜가 지날 때마다 힙 정렬 리스트에 추가 

              힙정렬 리스트에 포함되어야만 수입을 할 수 있는 것임 

                       5일날 동났는데, 4일날 수입해서 커버를 할 수있지만  // 29 일 수입하면 중간 시간동안 0이기 때문에 

 

 *** 2) 를 제대로 구현하기 위해서는 

       공급 날을 기준으로 해당 날짜의 stock 체크, 

       만약 그 날이 4일째 인데 재고가 3이면 (곧 동난다는 의미) ==> 힙 정렬에서 가장 큰 놈 뽑아서 수입시키기 

       반대로 재고가 20 이면 (아직 충분히 많으니까) ==> 우선 힙정렬에 추가해두기 (나중에 쓰도록) 

 

 

말로 하니까 더 헷갈리는데 코드를 살펴보면..! 

      

import heapq

def solution(stock, dates, supplies, k):
    start = 0
    cnt = 0
    h = [] # (현시점에서 수입 가능한) 수입 물량 힙으로 저장
    while stock < k: # 재고 개수 전체 k 개수 넘으면 반복 stop
    
        for i in range(start, len(dates)):
            if dates[i] <= stock: # 재고 남아있는 상황
                heapq.heappush(h,(-supplies[i],supplies[i])) # h리스트에 힙으로 저장해두
                start = i+1 #해외 수입가능 날보기
           
           else: # 재고 부족한 상황
                break 
                
        stock+= heapq.heappop(h)[1] # h에서 가장 큰 놈 추출해서 수입!
        cnt+=1
        
    return cnt

 

 

최대 힙 구현 방법 

heapq.heappush(h,(-supplies[i],supplies[i]))  으로 최대힙을 구현했다. 

튜플의 경우 [0] 을 기준으로 정렬이 되니까, 정렬하고자 하는 값에 -를 붙여서, 반대로 정렬이 되도록

 

 

 

 

3. 정리

힙... 어렵다 어려워.... 개념은 쉬운데 적용이 어렵다 어려워 

이 문제는 이해하기도 어렵다 어려워...