[LeetCode] - 1011_Capacity to ship packages within d days

문제 소개

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

풀이

public int shipWithinDays(int[] weights, int days) {
    int answer = 0;
    int left = 0, right = 0;
    for (int tmp : weights) {
        left = Math.max(left, tmp);
        right += tmp;
    }

    while (left <= right) {
        int mid = (left+right)/2;
        int day = 1, result = 0;

        for (int box : weights) {
            if (result + box > mid) {
                day++;
                result = 0;
            }
            result += box;
        }

        if (day <= days) {
            answer = mid;
            right = mid-1;
        } else {
            left = mid+1;
        }
    }

    return answer;
}

이번 문제는 이진탐색 문제로 제시된 일수에 알맞게 화물을 보낼 수 있는 적정 용량을 찾는 문제다.

접근 방법은 아래와 같다.

• `left`는 최소 적정 용량으로 실어야 하는 화물의 최대 용량이다.
  • 가장 큰 용량의 화물 하나는 실을 수 있어야 하기 때문이다.
• `right`는 최대 적정 용량으로 실어야 하는 화물 용량의 총 합이다.
  • 만약 days가 1일 때를 가정하여, 하루만에 화물을 모두 보낼 수 있어야하기 때문이다.
• `mid`는 예상 적정 용량으로 화물을 실어나가며 일수에 맞출 수 있는 최솟값인지 검사한다.

 

이번에도 문제를 풀고 다른 성능 좋은 해결책을 찾아보았고 몇가지 아이디어를 얻어 공유한다.

int left = 1, right = 25_00_0000;

첫번째로 left, right의 값을 제시 된 조건을 보고 초기 설정을 해주는 방법이다.

반복문을 돌리지 않아도 되니, 범위가 더 넓어지는 경우 고려해보면 좋을 것 같다.

if(weights.length == days){
    return max;
}

두번째로 early return을 이용해 특정 조건에 대한 답을 내놓는 방식이다.

days와 화물의 수가 똑같다면 하루에 하나씩 실어서 보내야 하므로 자연스럽게 화물의 최대 용량이 답이 된다.

이러한 조건으로 실행시간을 줄이는 것도 좋을 것 같다.

 

적용 전 / 적용 후