이분탐색을 활용한 알고리즘 문제풀이

오늘 푼 문제: Capacity To Ship Packages Within D Days

입출력

• 입력: 각 화물의 무게인 정수배열 weights, 주어진 시간의 값인 days가 주어집니다.
• 출력: days안에 들어올 수 있도록 화물을 적재할 때 가장 적게 적재할 수 있는 값을 return합니다.

예제 코드

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lt = Arrays.stream(weights).max().getAsInt(), rt = Arrays.stream(weights).sum(), answer = Integer.MAX_VALUE;
        while(lt <= rt) {
            int mid = (lt + rt) / 2, sum = 0, cnt = 0;
            for (int i = 0; i < weights.length; i++) {
                if (weights[i] == mid) {
                    cnt++;
                    if (sum != 0) cnt++;
                    sum = 0;
                } else {
                    sum += weights[i];
                    if (sum >= mid) {
                        cnt++;
                        if (sum == mid) sum = 0;
                        else sum = weights[i];
                    }
                }
            }
            if (sum != 0) cnt++;
            if (cnt <= days) {
                rt = mid - 1;
                answer = Math.min(answer, mid);
            }
            else lt = mid + 1;
        }
        return answer;
    }
}

• 가장 무거운 화물의 무게 ~ 각 화물 무게의 총합의 범위에서 이분탐색을 진행하였습니다.
• 해당 무게로 적재할 때 몇일이나 걸리는지를 확인한 후 범위를 조정하였습니다.

회고

• 스코프에 유의하며 코드를 작성해야할 것 같습니다.