[python3] 1011. Capacity To Ship Packages Within D Days

풀이 일자: 23.02.22

난이도: [Medium]

분류: [Binary Search]

문제 내용

weights라고 하는 배열에 순서대로 옮겨야 할 물건의 무게가 들어있고 days라는 변수에는 옮기는데 주어진 시간이 들어있다. weights에 들어있는 물건 순서대로 물건을 배로 옮기는데 하루에 배로 옮길 수 있는 최대 무게가 최소화되도록 옮긴다고 했을 때 배의 capacity를 구하는 문제이다.

 

weights = [3,2,2,4,1,4], days = 3

만약 위의 배열이 주어졌을 때 (3,2), (2,4), (1,4)로 옮긴다면 최대무게가 6이 된다.

만약 (3,2,2), (4,1), (4) 이렇게도 옮길 수 있는데 이럴 경우 최대무게가 7이 된다.

=> 이러한 최대무게중 최소가 되도록 물건을 days안에 옮기는 문제이다.

 

 

문제 해결 흐름

1. 처음의 접근방식이 너무 어려웠다. 이진탐색으로 뭘 어떻게 해야하는지... 우선 내야 하는 답에 집중해보자..

→ 우선 무게를 최대한 나눠야 하기 때문에 days를 모두 사용해야 한다.

 

2. 이진탐색이라고 해서 현재 주어진 배열을 가지고 이진탐색을 할 수 있을까를 생각해보자. 

→ 여러 방법을 생각하더라도 어려울 것이라는 생각이 들 수 있다. 그 이유는 이진탐색은 정렬된 배열에서 사용가능하기 때문이다.

 

3. 답이 될 수 있는 범위를 생각해보자.

→  weights의 최대무게를 가진 물건을 최소한 실어야 하기 때문에 최소값은 max(weights)이다. 

→ 최악의 경우는 모든 물건을 한번에 실어나르는 방법으로 최대값은 sum(weights)가 될 것이다.

 

4.답의 범위가 최소, 최대값을 가지고 있고 연속된 수이며 정렬되어 있으니까 이진탐색을 해당 범위 내에서 해야겠다.

→ 이진탐색의 mid가 최대 capacity라고 가정하고 나눠봤을 때 days안에 해결이 가능한지 확인한다.

→ 만약 days안에 해결이 된다면 최대 capacity를 너무 많이 잡은 것이다. mid로 right를 옮긴다.

→ 만약 days안에 해결이 안된다면 최대 capacity를 너무 적게 잡은 것이다. mid +1로 left를 옮긴다.

 

=> 위의 아이디어를 코드로 옮긴다면.

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        l, r = max(weights), sum(weights);

        while(l < r):
            mid = l + (r - l)//2;

            if (self.possible(weights, days, mid)):
                r = mid;
            else:
                l = mid + 1;       
        return l;


    def possible(self, weights: List[int], days: int, capacity: int) -> bool:
        currentWeight = 0;
        for w in weights:
            if (w + currentWeight) > capacity:
                days -= 1;
                currentWeight = 0;
            currentWeight += w;

        return days > 0;

=> 사실 이진탐색을 떠올리기 어렵고 이진탐색을 떠올렸다고 하더라도 weights를 가지고 이진탐색을 해보려고 하지 또다른 정보를 만들어내서 여기에 이진탐색을 적용하기는 더욱 어려워 보인다.

 

Time Complexity: O(NlogN)

시간복잡도는 NlogN을 가질 것이다.  이진탐색 내부에 해당 capacity로 잘랐을 때 얼마나 걸리는지 계산하는 과정에서 for문을 사용하기 때문이다.

 

Space Complexity: O(1)

배열을 사용하지 않고 여러 변수만을 추가로 정의해서 사용하기에 O(1)의 공간복잡도를 가진다.

 

 

다른 해결 방식

함수를 내부에 넣은 것, 함수를 사용하지 않고 푼 것 등 구조의 차이일 뿐 idea의 유의미한 차이는 없었다.

 

 

문제 링크

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

Capacity To Ship Packages Within D Days - LeetCode