[코테연습] 1011. Capacity To Ship Packages Within D Days

금일은 이분탐색을 할 수 있는 문제를 풀었다.

 

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

 

저번에 기록했던 문제와 동일하게 이분탐색 구조의 문제라는 것을 확인한 뒤 check() 함수만 잘 구현하면 풀 수 있는 문제이다.

 

먼저 low, high 를 초기화 한다.

 

int low = 0;

int high = weights[0] * 50_000; // 문제 조건 중 weights[i] 와 length 값이 5 * 10^4 것을 고려한 최대값

 

이분탐색을 위해 while 문을 작성한다.

 

       while(low <= high) {

            int mid = (low+high)/2;

            if (check(mid, weights, days)) {

                high = mid-1;

            } else {

                low = mid+1;

            }

        }

 

check() 함수가 true 일때는 mid 의 값이 허용된 것이므로 high 로 놓고, false 일때에는 mid 값이 허용되지 않았으므로 low 로 놓으면서 점점 범위를 좁혀나간다.

 

중요한 것은 check() 함수 이다.

 

weights 의 element 를 더해가면서 mid 보다 크면 day 를 증가시는 방식으로 구현한다.

완성된 코드는 다음과 같다

 

class Solution {
    public int shipWithinDays(int[] weights, int days) {

        int low = 0;
        int high = weights[0]*50_000;

        while(low <= high) {
            int mid = (low+high)/2;
            if (check(mid, weights, days)) {
                high = mid-1;
            } else {
                low = mid+1;
            }
            // System.out.println("["+low+", "+high+"] = "+mid);
        }
        return low;
    }
    boolean check(int mid, int[] weights, int days){
        // System.out.println("check mid : "+mid);
        int day = 1;
        int acc = 0;
        // System.out.println();
        for(int i = 0; i < weights.length;) {
            int w = weights[i];
            if ((w+acc) <= mid) {
                acc+=w;
                i++;
            } else {
                acc = 0;
                day++;
            }
            // System.out.println("day : ["+day+"] // acc : ["+acc+"] // w : ["+w+"]");
            if (day > days) {
        // System.out.println("rs day ===> "+day);
                return false;
            }
        }
        // System.out.println("day ===> "+day);
        if (day <= days) {
            return true;
        }
        return false;
    }


}