99클럽 코테 스터디 23일자 TIL + capacity-to-ship-packages-within-d-days

문제 출처

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

학습 키워드

이분탐색

시도 방법

이전 TIL 22일자의 방식을 이용했다.

가장 최대 용량은 하루에 모든 용량을 보내는 것이다.

따라서 [1,2,3,4,5] 라는 무게가 있다면 최대 용량은 합계인 15가 되겠다.

start 0 ~ end 15 사이를 이분법으로 탐색해 최적의 용량을 찾았다.

내가 작성한 코드

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

        int start = 0 ;         
        int end =  0; 

        for(int i = 0 ; i<weights.length; i++) {
            end += weights[i]; 
        }
        int mid = 0 ; 
        int answer = 0 ;
        int nowWeight = 0 ; 
        int load = 0 ; 

        while(start <= end) {
            
            mid = (start+end)/2 ; //capacity
            load = 0 ; 
            nowWeight = 0 ; 
            
            for(int weight : weights) {
                
                if(weight > mid) {
                    load = days + 1 ; 
                    break; 
                }

                if(nowWeight + weight > mid) {
                    load += 1 ; 
                    if(load > days) break; 
                    nowWeight = weight ;
                } else {
                    nowWeight += weight ; 
                }
            }   
            load +=1 ; 

            if(load > days) {
                start = mid+1; 
            } else {
                answer = mid ; 
                end = mid -1; 
            }
          
        }
        return answer ;
    }
}

코드설명

반복적으로 최대 capacity를 지정해놓고 각 배열의 무게를 더했을때 제한을 걸었다.
(1) 만약 무게가 capacity 자체를 넘어버리면 무조건 stop
(2) 만약 무게의 합이 capacity를 넘기면 load 처리함 (하루 보냈다는 의미)
load가 days를 넘겨버리면 이미 허용 일자를 초과했으므로 stop 처리
(3) 가장 마지막 짐을 보내야 하므로 load를 +1 처리함

여기서 days 보다 load가 크다는 말은 날짜내로 보내기에는 허용량(capacity)가 너무 작다는 의미이므로 시작점을 mid + 1 로 다시 잡아준다.

반대로 days 보다 load가 작다면 답일 수도 있고, 혹은 더 작은 허용량을 찾을수도 있으므로 최대허용량을 mid - 1 로 하여 추가 검색을 한다.

출력결과

새롭게 알게된 점

이전 문제는 도움을 받았는데 이번에는 이전에 배웠던 내용을 활용해 문제를 풀 수 있어 한층 성장함을 느낄 수 있었다.

다음에 풀어볼 문제 - ??

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL