[LeetCode] 1011 Capacity To Ship Packages Within D Days

💡  오늘의 학습 키워드

📌  이분 탐색

 

문제 설명

문제 링크 : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i].
Each day, we load the ship with packages on the conveyor belt (in the order given by weights).
We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages
on the conveyor belt being shipped within days days.

제한 사항
1. 1 <= days <= weights.length <= 5 * 10^4
2. 1 <= weights[i] <= 500

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

이 문제의 목표는 주어진 날짜 내에 모든 패키지를 운송하기 위해 필요한 배의 최소 적재 용량을 찾는 것입니다.
배의 적재 용량이 가장 작은 값부터 가장 큰 값 사이를 탐색하는 문제로 이진 탐색이 가장 효율적인 솔루션이 됩니다.
완전 탐색을 사용한 풀이도 가능하겠지만 패키지의 무게 합이 크면 클수록 시간이 오래 걸리는 문제가 있습니다.
이진 탐색의 경우 찾고자 하는 최소 용량이 특정 범위 내에 있다는 점과 이 범위 내에서 적절한 용량을 찾기 위해
결정 문제를 반복적으로 해결하는 것이 효율적이기 때문입니다. 문제 해결과정은 다음과 같습니다.

1. 'left'는 패키지 배열의 최대값(최소값)으로, 'right'는 패키지 배열의 총합(최대 용량)으로 설정합니다.
2. 'mid' 값 (중간 값)을 현재 적재 용량 후보로 설정합니다.
3. 주어진 적재 용량으로 모든 패키지를 몇 개의 날에 운송할 수 있는 지 계산합니다.
4. 계산한 날의 수가 주어진 날보다 작거나 같으면 적재 용량을 줄여 더 작은 용량으로 운송할 수 있는지 확인합니다.
5. 계산한 날의 수가 크면 적재 용량을 늘려서 최적의 용량을 탐색합니다.

 

이분 탐색 과정의 이해를 위해서 다음 예시를 들어보겠습니다.
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 3

가장 작은 용량은 10, 가장 큰 용량은 1~10의 합인 55이고 첫 번째 적재 용량 후보 값인 32에서 탐색을 시작합니다.
적재 용량에 따른 계산 날짜를 통해 이분 탐색 범위를 조정할 것입니다.

이후 이분 탐색 과정은 다음과 같고, 최종 output인 최종 적재 용량으로 15 가 나오는 것을 확인할 수 있었습니다.

 

결국 적재 용량을 설정하는 left, right 값 세팅과 중간 값을 적재 용량 후보로 두고 주어진 날짜에 맞게 나누는 과정이 핵심이었습니다.
이분 탐색 발상 과정과 중간 값을 이용하여 적절한 값을 탐색해 나가는 과정을 이해할 수 있어야 합니다.

 

💡 내가 해결한 방식은?

class Solution:
    def shipWithInDays(self, weights: List[int], days: int) -> int:
        def canShipInDays(weights, days, capacity):
            curr_weight = 0
            day_needed = 1
            for weight in weights:
                if curr_weight + weight > capacity:
                    curr_weight = 0
                    day_needed += 1
                curr_weight += weight
            
            # 적재하는데 필요한 날과 주어진 날짜를 비교 
            return day_needed <= days
        
        left, right = max(weights), sum(weights)
        
        while left < right:
            mid = (left + right) // 2
            if canShipInDays(weights, days, mid):
                right = mid
            else:
                left = mid + 1
                
        return left

 

---

✍️  TIL

DP를 생각하거나 이분 탐색을 생각할 때도 항상 처음 정의를 어떻게 하는지가 중요한 거 같고, 특히
이분 탐색을 사용해야겠다고 생각하는 과정에서 최소, 최대 값을 어떻게 설정할지 잘 생각해야 
그 다음 값을 탐색하는 로직을 구현하는 과정까지 올바르게 나아갈 수 있다는 것을 알수 있었다.
이분 탐색을 사용했을 때 생각해야 할 포인트들을 잘 학습할 수 있었고 잘 숙지해서 다음 이분 탐색 문제에서
활용할 수 있었으면 좋겠다.