Daily LeetCode Challenge - 1011. Capacity To Ship Packages Within D Days

Problem From.

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

오늘 문제는 컨베이어 벨트에 짐들이 순서대로 실려올때, 주어진 날짜 내에 모든 짐들을 다 옮긴다고 할때 한번에 옮길수 있는 최소의 짐의 무게를 구하는 문제였다.

먼저 weight array 를 처음부터 끝까지 보면서 최대 짐의 무게의 합을 구한다.

그 다음 binary Search 를 이용하여, 현재 짐의 무게를 가지고 가면서, 그 무게가 다음 순서의 짐을 더하게 되었을때, 최소 짐의 무게를 넘지 않는지 검사한다. 넘으면, day 를 하나 추가해주는 식으로 주어진 days 안에 들어갈 수 있도록 하였다.

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        
        var maxWeight = 0
        var maxSum = 0
        
        weights.forEach {
            maxWeight = Math.max(maxWeight, it)
            maxSum += it
        }
        
        while(maxWeight < maxSum) {
            
            val mid = (maxWeight + maxSum) / 2
            var need = 1
            var curr = 0
            
            weights.forEach {
                if(curr + it > mid) {
                    need += 1
                    curr = 0
                }
                curr += it
            }
            
            if(need > days) maxWeight = mid + 1
            else maxSum = mid
            
        }
        
        return maxWeight
    }
}