[Java] Daily LeetCode Challenge 1011. Capacity To Ship Packages Within D Days

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

Capacity To Ship Packages Within D Days - LeetCode

 

풀긴 풀었는데, 제출하고 나니 여러 부분에서 거의 꼴등이었던 문제..

효율적인 이진 탐색을 자주 이용하자! 아직 이진 탐색에 대한 사용이 익숙치 않고, 더 공부해야겠다고 느낀 문제였다.

 

※ 이진 탐색 사용

1. 패키지의 크기는 maxSize ~ totSize 사이

• 크기가 maxSize 미만이면 가장 큰 물건은 실을 수 없음
• 크기가 totSize이면 어떤 물건이든 실을 수 있음
• maxSize = 가장 큰 물건의 크기

2. 해당 사이즈를 사용했을 경우

• day가 남으면 right = mid
• day가 부족하면 left = mid+1
• right == left가 되면 loop 탈출, 해당 값이 정답

 

 

[나의 코드] - 96ms

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int tot = 0, max = 0;
        for(int i : weights){
            tot += i;
            max = Math.max(i, max);
        }
            
        int size = tot / days;

        if(size < max)
            size = max;

        while(true){
            int day = 0, sum = 0;
            for(int i : weights){

                if(sum + i < size){
                    sum += i;
                }else if(sum + i == size){
                    sum = 0;
                    day++;
                }else{
                    sum = i;
                    day++;
                }
                if(day > days)
                    break;
            }

            if(day == days && sum > 0 || day > days){
                size++;
                continue;
            }
            break;
        }

        return size;
    }
}

 

[정석 코드] - 11ms

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int tot = 0, max = 0;
        for(int w : weights){
            tot += w;
            max = Math.max(w, max);
        }

        int l = max, r = tot;

        while(l < r){
            int mid = (l+r)/2, day = 1, cur = 0;

            for(int w : weights){
                cur += w;
                
                if(cur > mid){
                    day ++;
                    cur = w;
                }
            }

            if(day <= days)
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }

}