최소 공급 찾기

본 문제는 스파르타 코딩에서 제공된 문제입니다.

[문제 설명]

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

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

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

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

가장 먼저 이 문제가 요구하는 것이 무엇인지, 그 요구 조건을 충족시키기 위해선 어떤 방식으로 접근해야 되는지 확인해보자. 일단 이 문제는 '밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지'를 요구하고 있다. 즉, 공급 받을 횟수의 최솟값을 구하라는 것이다. 그렇다면 이를 어떻게 구현해야 할까? 이 문제도 사실 어떤 정해진 유형은 없다. 즉, 스택을 써야 하고 큐를 써야 하고... 이러한 점이 없는 그냥 일반적인 문제이다. 결국 이문제의 핵심은 유형의 파악이라기 보다는 어떻게 효율적으로 구현하느냐에 있다. 공급받는 횟수에 대한 모든 경우의 수에 대해서 구한 후, 최솟값을 구할지. 아니면 최적의 공급 수를 바로 찾아가야 할지에 대한 고민을 해야 한다. 이 문제 같은 경우는 두 방법을 동시에 사용한다고 생각해도 된다. 즉, 모든 경우의 수를 구한 후 판단하는 것이 아닌,해당 조건에 맞을 때까지 공급의 수를 늘려가면서 확인하고, 조건이 완료된다면 그 값을 반환하면 된다. 이제 본격적으로 구현을 시작해 보자.

---

[문제 풀이]

일단 먼저 stock을 받아야 할 때마다 받아 오는 것이 아닌, 받을 것에 대한 계획을 짠다고 생각해야 한다.

즉, 날짜가 지나면서 공급일에 받는 상황이 아닌 공급을 실질적으로 받기 전, 어느 날에 공급을 받을 지 계획을 짜는 코드이다. 그렇게 되면 생각해야 될 부분은 내가 가지게 되는 stock이 버터야 한 날까지 버틸 수 있냐의 판단이다.

즉, stock은 외부로 부터 공급을 받아오면서 쌓이게 될 것이고 내가 현재 짜고 있는 계획을 통해서 k날까지 버틸 수 있다 하면 이 코드는 종료된다.

그럼 이제 어느 날에 공급을 받아야 가장 효율적인지에 대한 계획을 짜는 핵심적인 부분이다. 여기서는 내가 현재 가지고 있는 혹은 공급받을 stock의 수(공급받는 계획이므로, 공급을 받았다고 가정하는 부분)로 버틸 수 있는 날까지의 가장 최대 공급량의 날짜를 선택하는 것이다. 최소로 받아오며 가장 효율적으로 받아와야 하기에, 내가 버틸 수 있는 날까지에서의 최대 공급량을 받아오면 된다는 뜻이다. 이렇게 하면 이 문제는 풀린다. 이제 이를 상기시키며 코드를 짜 보자.

import heapq # O(NlogN)

def get_min_supply(stock, dates, supplies, k):
    idx = 0 # 날짜를 훑는 인덱스
    sup_cnt = 0 # 공급 받은 횟수
    heap = [] # 최대값을 뽑기 위한 힙(리스트)
    while stock < k: # 버티지 못한다면 공급 받음-> k날까지 버틸 수 있다고 판단하면 while문 종료
        while idx < len(dates) and dates[idx] <= stock: # idx의 범위 설정 및 버틸 수 있는 날까지 탐색
            heapq.heappush(heap, -supplies[idx]) # 최댓값을 뽑기위해 해당 공급량을 heap에 넣어줌 (최대값을 위해서 -을 붙임)
            idx += 1 #다음 date로 넘어감

        max_sup = -heapq.heappop(heap) # 버틸 수 있는 date까지에서의 가장 많이 받을 수 있는 공급량
        stock += max_sup # 그 공급량을 받는다고 가정(계획을 세운다고 생각하면 됨)
        sup_cnt += 1 # 공급 횟수 +1

    return sup_cnt

 

※ 최댓값을 산출할 때, max() _ [O(N^2)] 를 사용하지 않고, 시간 복잡도를 고려하여 heap _ [O(NlogN)]을 통해 구했다.

---

---

[잘못된 풀이]

내가 이 문제를 처음 접근했을 때는 일단 날짜를 보내면서, 부족할 때마다 공급을 받아야겠다고 잘못 판단했었다. 하지만 이 문제는 애초에 최소로 공급을 받아야 하므로 실제로 날짜를 보내면서 공급을 받으려고 생각하면 고려해야 할 상황이 너무나 많아서 복잡해진다. 즉, 공급받는 것을 시작하기 전에 미리 계획을 짜야한다. 이 부분에 있어서 처음부터 잘못 접근했기 때문에 제대로 된 풀이로 다시 들어가기까지 오랜 시간을 낭비했다.

---

[문제 평가]

이 문제는 결론적으로 코드만 본다면 그렇게 어려운 문제는 아니다. 하지만, 어떻게 접근하고 시작하냐에 따라 이 문제를 맞히냐 못 맞히냐가 갈리는 것 같다. 이러한 문제들은 풀면서 그 상황에 맞게 코드를 짜기보다는 미리 어떻게 구현하여 결론까지 도달할지에 대한 계획을 세우고 시작해야 할 것 같다.