99클럽 코테 스터디 23일차 TIL + 이분탐색(Capacity To Ship Packages Within D Days)

오늘의 과제

리트코드 Medium으로 분류된 Capacity To Ship Packages Within D Days입니다.

 

이번 유형은 Binary Search(이분탐색) 입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

입력으로 각 화물의 무게 배열인 weights와 화물을 처리해야 하는 기간인 정수 days가 주어 질 때

기한 내 모든 화물을 처리할 수 있는 화물선의 최소 용량을 반환하면 됩니다.

 

이전 문제와 마찬가지로 lt, rt, mid만 선별해낼 줄 알면 쉽게 풀 수 있는 문제입니다.

 

먼저 최소값, 최대값을 구해보겠습니다.

 

문제의 요구 사항중 weights를 모두 처리해야 한다고 나와있습니다. 여기서 유추할 수 있는 점은 모든 화물을 처리해야 하니 선박의 최소 용량은 weights중 가장 무거운 값임을 알 수 있습니다. 그렇다면 최대 용량은 자연스레 주어진 화물의 총 합이 될 것 입니다.

 

 

이제 lt와 rt를 선별했으면 문제 내 요구사항을 도달하기 위한 약간의 if문만 섞으면 됩니다. lt, rt, mid는 선박의 총 용량을 뜻하고 있으니 각 화물을 싣다가 mid 값이 넘어간다면 그 날에는 더 이상 실을 수 없으니 하루가 지난걸로 간주하고 화물의 합을 초기화 시켜주면 됩니다.

 

 

이해가 안되는 부분은 코드와 주석을 참고해주세요.

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        // 초기값 설정
        int lt = 0, rt = 0, mid = 0, answer = 0;

        // lt는 화물 중 제일 무거운 값 (최소 값)
        // rt는 총 화물의 합계
        for (int i : weights) {
            lt = Math.max(lt, i);
            rt += i;
        }

        // 하루밖에 주어지지 않았다면 화물의 전체 무게만큼 선박 용량이 필요하다
        if (days == 1) return rt;

        while(lt <= rt) {
            mid = (lt + rt) / 2;
            if (isPossible(weights, mid, days)) {
                rt = mid - 1;
                answer = mid;
            } else {
                lt = mid + 1;
            }
        }
        return answer;
    }

    private boolean isPossible(int[] weights, int mid, int days) {
        int sum = 0;
        int cntDays = 1;

        for (int weight : weights) {
            sum += weight;
            // 선박 용량을 초과했을 경우
            if (sum > mid) {
                sum = weight;
                cntDays++;
            }
        }
        
        return cntDays <= days;
    }
}

 

 

배운 점

확실히 문제 유형별 하나 풀고 바꾸고 보다는 해당 유형을 반복해서 푸는게 익숙해지는데 조금 더 도움이 되는 것 같습니다. 벌써 세 번째 이분탐색을 풀어보니 기존 푸는 방법에서 최소 값, 최대 값만 잘 구해내면 나머지는 약간의 분기 처리만 해주면 된다는게 보이기 시작했습니다.

 

물론 아직은 낮은 난이도의 문제들로 선별되어 있어 자신감이 올라가 있는 상태이지만 저도 모르는 사이에 올라가는 난이도에 적응하여 오래 걸리지만 풀어낼 수 있는 실력이 길러지길 바래봅니다.

 

 

오늘의 한줄평

더닝 크루거 효과를 조심하자. 나는 아직 아무것도 모른다.