[99클럽 코테 스터디 23일차 TIL] LeetCode | 1011. Capacity To Ship Packages Within D Days

23일차 BInarySearch

Problem

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Sol

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # days 동안 다른 항구로 짐 옮기기
        # i 번째 짐 무게 == weights[i] 주어진 순서대로 실어야함
        # 각 날마다 컨베이어 벨트 위의 짐들을 배로 옮길거야
        # weight <= ship's max cap

        # return : least weight cap

        # 이진 탐색 : 짐을 나누는게 맞나? 왼쪽, 오른쪽 합 중 가벼운쪽 return
        # 근데 이제 탐색을 days 번 해야하네
        left = 1
        right = len(weights)+1

        least_cap = 0

        for _ in range(days):
            mid = (left + right) // 2
            if sum(weigth[left:mid]) < sum(weight[mid+1:right]):
                least_cap = sum(weight[left:mid])
                left = mid + 1
            else:
                least_cap = sum(weight[mid+1:right])
                right = mid

        return least_cap

합을 구해야한다는 생각이 있었는데 잘못되었습니다. 하다가 뭔가 잘못된 것 같아서 GPT와 함께 고쳤습니다...

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # days 동안 다른 항구로 짐 옮기기
        # i 번째 짐 무게 == weights[i] 주어진 순서대로 실어야함

        # 이진 탐색 : 짐을 나누는게 맞나? 왼쪽, 오른쪽 합 중 ㅁㅜㄱㅓㅇㅜㄴㅉㅗㄱ return?
        
        def isPossible(weights, days, capacity):
            cur_weight = 0
            days_need = 1
            
            for weight in weights:
                if cur_weight + weight > capacity:
                    days_need += 1
                    cur_weight = 0
                    if days_need > days:
                        return False
                cur_weight += weight
            return True
        
        # needs of capacity at least
        left = max(weights)
        # maximum
        right = sum(weights)
        
        while left < right:
            mid = (left+right)//2
            # isPossible to move during the days?
            # Yes~
            if isPossible(weights, days, mid):
                right = mid
            # Nope
            else:
                left = mid + 1
                
        return left

여러 방면으로 생각이 필요했던 문제였습니다. 무게의 합과 days를 생각하는 부분을 isPossible 함수로 뺐습니다.
⭐️ 이진 탐색을 사용하여 최소 용량을 찾습니다. 용량의 범위는 각 짐의 최대 무게(left)부터 모든 패키지의 총 무게(right)까지 입니다. mid를 기준으로 해당 용량이 가능한지 확인합니다. isPossible 이라면 더 작은 용량을 시도하고, 불가능하다면 더 큰 용량을 시도합니다.

1. 이진 탐색 설정
- left
- right

2. 이진 탐색 과정
- mid
- isPossible 함수를 사용하여 mid 용량으로 모든 짐을 주어진 days 안에 옮길 수 있는지 확인
- 가능하다면 'right = mid' 더 작은 용량 시도
- 불가능하다면 ‘left=mid+1' 더 큰 용량 시도

3. 결과 반환
- 이진 탐색 끝나면 적어도 left씩은 실어야 함을 알 수 있음