티스토리 뷰

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42629

 

코딩테스트 연습 - 라면공장 | 프로그래머스

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량

programmers.co.kr

import heapq

def solution(stock, dates, supplies, k):
    answer = 0
    idx = 0
    h = []
    
    while(stock<k):
        for i in range(idx,len(dates)):
            if dates[i]<=stock:
                heapq.heappush(h,-supplies[i])
                idx=i+1
            else:
                break

        stock -= heapq.heappop(h)
        answer += 1
        
    return answer

설명

 

stock의 합이 k를 넘을때까지 다음 과정을 반복한다.

 

만약 stock이 떨어지기 전까지(0이 되기 전까지) 여러 개의 날에서 공급을 받을 수 있다면 그중 가장 많은 양을 받아오는 것이 이득이다. 왜냐하면, 우리는 최소한의 공급을 받고 싶으니까!

 

여기서 힙을 사용해 최대값을 빼오고 stock에 더하면 된다. 최대힙을 만들기 위해 push할때 -를 붙여줬다.

 

힙에서 최대값을 뺀 나머지 값들을 초기화시키지 않고 남겨두는 이유는 위에서 말했듯이 가장 많은 양을 받아오는 것이 이득이기 때문이다. 예를들어, 힙에 [5, 10]이 먼저 들어와 있다고 하자. 그러면 여기서 가장 먼저 10이 빠질텐데 며칠뒤에 3이 들어왔다고 하면 힙은 [3, 5]가 된다. 3이 제일 마지막에 들어왔지만 먼저 들어왔던 5를 받아놓는다면 2개의 밀가루를 이득보는 것이다. 

 

아무튼. 처음에 힙을 어떻게 사용해야할지 잘 몰라서 애를 먹었지만, '라면공장'과 같은 최대 혹은 최소한의 횟수를 찾는 경우 유용하게 쓸 수 있는 자료구조라고 생각한다. 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함