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

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

 

문   제 : 

짐의 무게를 뜻하는 일차원 정수배열로 이루어진 weights[] 가 주어진다.

그리고 나눠서 운반해야하는 날짜 days가 주어진다.

이 짐들을 배에 실어서 days에 걸쳐 모두 날라야한다.

배의 용량을 최소로 해서 나를수 있는 용량을 구하여라.

 

Constraint

{ 1 <= days <= weights.length == 5 * 10^4 }

{ 1 <= weights[i] <= 500 }

 

 

Example )

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, 
so using a ship of capacity 14 and splitting the packages into parts 
like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

//////////////////////////////////////////////////////////

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

//////////////////////////////////////////////////////////

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

 

---

접   근 : 

capacity가 가질 수 있는 최대와 최소값을 정하고 범위를 점점 좁혀서 최소값을 구한다.

---

해   결 : 

가장 무거운 짐을 구해서 capacity의 최소값을 구한다.

모든 짐의 합을 구해서 capacity의 최대값을 구한다.

구한 범위로 시작해서 capacity의 최대값, 최소값의 평균으로 capacity를 잡고

이 capacity로 배의 운반이 가능한지 불가능한지를 체크한다.

만약, 가능하다면 capacity 최대값을 capacity의 최대값, 최소값의 평균으로 줄여도 된다는 뜻이다.

만약, 불가능하다면 capacity의 최소값을 올려주면서 다음에는 가능한지 체크해보면 된다.

---

결   과  :

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        // 가장 무거운 짐 -> 짐을 아무거나 집었을 때 최소 하나를 보낼 수 있게 하는 최소 값 -> capacity의 최소 설정
        int capaMin = Arrays.stream(weights).max().getAsInt(); 

        // 모든 짐의 합 -> 하루에 모든 짐을 전부 다 보낼 수 있게 하는 값 -> capacity의 최대 설정
        int capaMax = Arrays.stream(weights).sum(); 

        // while을 반복하면서 capacity의 범위를 좁혀가면서 찾는 방법이다. -> 목표는 capaMax를 최대한 줄이는 것.
        while(capaMin < capaMax){
            int mid = (capaMin + capaMax) / 2; // 임의의 capacity 설정 (중간값으로)
            if(possible(weights, days, mid)) // mid 값의 capacity로 가능한지 체크
                capaMax = mid; // 가능하다면 최대로 하는 값 가능한 만큼 줄임
            else
                capaMin = mid+1; // 운반 불가능 할 시 최소 capacity 한 칸 올려줌
        }
        
        return capaMax;
    }

    public boolean possible(int[] weights, int days, int capacity){
        int currWeight = 0;
        int countDays = 0;

        for(int weight : weights){
            if(weight + currWeight > capacity){
                currWeight = 0;
                countDays++;
            }
            currWeight += weight;
        }
        return countDays < days;
    }
}