[프로그래머스 힙]라면 공장 - Python3

문제

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

알고리즘

def solution(stock, dates, supplies, k):
    import heapq as hq
    answer = 0
    heap = []
    j = 0

    # stock이 k보다 작을 동안 반복한다
    while stock < k:
        # dates배열을 순회한다.
        for i in range(j, len(dates)):
            # dates배열을 순회하면서, stock이 dates[i]보다 큰 곳을 찾는다.
            # 왜 이러냐면, 공급받는 횟수를 줄이기 위해서 그러는 것인데,
            # 좀 쉽게 말하자면 버틸수 있을 때까지 버티는 것이다.
            if dates[i] <= stock:
                # 공급 받을수 있는 것 중 제일 큰 값을 받기 위해서, supplies[i]를 heap에 push한다
                hq.heappush(heap, (-supplies[i], supplies[i]))
                j = i + 1

            # 공급받아야 하는 시점에서 멈춘다.
            else:
                break;

        # 힙에서 나온 값을 temp에 저장한다. 이 값은 supplies에서 큰 순서대로 저장된다. 
        # 그러다가 stock이 k보다 커지는 순간, 반복을 멈추고 answer를 리턴한다. 
        temp = hq.heappop(heap)[1]
        stock += temp
        answer += 1

    return answer

stock = 4
dates = [4, 10, 15]
supplies = [20, 5, 10]
k = 30
print(solution(stock, dates, supplies, k))

설명

현재 가지고 있는 stock이 k보다 클 때까지 반복한다. 그리고 for문을 통해 dates배열을 순회하면서, dates[i]보다 stock값이 작다면 supplies[i]를 heap에 넣는다. 이때, 파이썬의 heapq는 최소힙을 제공하므로, 큰 것이 먼저 나오게 하기 위해
(-suppplies[i], supplies[i])의 튜플로 만든 후, pop한 원소의 [1]번쨰 원소를 취한다. 그리고 그 값을 stock에 더해준다. 그러고 answer의 값 또한 증가시킨다. 

결과

올바른 값을 출력한다.

후기

너무 어려웠다. 사실 문제가 그렇게 어려운게 아닌거 같은데, 내가 너무 생각을 많이한 것 같다. k라는 시점은 사실 시점을 말하는게 아니라, 확보해야하는 총량이라고 생각하면 좀더 편하게 풀 수 있다. 또한, 각 dates[i]는 시점이라고 할 수도 있지만 이러면 머리가 굉장히 아프니까, dates[0]이 4라는 것은 4일이 되는 시점까지 4만큼의 밀가루가 필요하다고 생각하면 된다.

이것을 좀 쉽게 풀어서 말하자면, 일단 지금 가진 stock이 모자랄 때까지 버티면서 힙에다가 공급받을 수 있는 값들을 넣는다(supplies[i]). 그러다가 어느 date[i]가 지금 가진 stock보다 커진다면, 힙에 있는 것 중 제일 큰 값을 꺼내서 stock에 더한다. 

물론 이러한 설명도 굉장히 조악한 것을 나도 아주 잘 알고 있다. 왜냐하면 나는 아직도 이 코드가 왜 제대로 돌아가는지를 모르기 때문이다. 그렇지만, 힙을 사용하는 문제의 틀을 좀 더 잘 이해했다고 생각한다.