99클럽 코테 스터디 21일차 TIL, 이분법(Capacity To Ship Packages Within D Days)

1. 문제 정의

2. 문제 접근

정해진 기간 내에 어느 무게로 해야 딱 정해진 기간에 끝낼 수 있는지 찾는 문제다. brute force 를 이용하여 완전탐색을 하면 문제를 풀 수 있지만, 그렇게 하면 시간 복잡도가 n의제곱이 되어 시간초과가 날 것이다. 그래서 nxlogn을 쓰면 정해진 시간 내에 문제를 해결할 수 있을 것 같다.

3. 문제 풀이

1. 두 포인트를 구한다.
2. 두 포인트의 중앙을 구하여 정해진 기간 내에 통과가 되는지 확인한다.
3. 계속 범위를 좁혀나간다.
4. 답을 리턴한다.

4. 코드

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int sum = 0;
        int max = 0;
        for(int w:weights){
            sum += w;
            max = Math.max(max,w);
        }

        int left = max;
        int right = sum;
        int ans = 0;

        while(left <= right){
            int mid = (left + right) / 2;
            int wSum = 0;
            int wCnt = 1;
            for(int i = 0; i < weights.length; i++){
                wSum += weights[i];

                if(wSum > mid){
                    wCnt++;
                    wSum = weights[i];
                }
            }
            if(wCnt <= days){
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

 

 

5. 회고

그전에 풀었던 입국심사 문제와 유형이 비슷한 것 같다. 이분탐색의 응용?버전의 문제로 느껴진다. 이분탐색에서 제일 핵심은 범위를 어떻게 좁혀 나가는지다. 통과되는데 걸린 시간이 days보다 작거나 같을 경우 right값을 땡김으로써 mid 값을 줄여 더 걸리는 시간을 늘려준다. 항상 이분탐색을 풀 때 왼쪽을 땡겨야할지, 오른쪽을 땡겨야 할지 헷갈린다. 문제를 더 풀어보며 확신을 가지자!