99클럽 코테 스터디 23일차 TIL + [LeetCode] 1011. Capacity To Ship Packages Within D Days JAVA풀이/ 이분탐색

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

1011. Capacity To Ship Packages Within D Days JAVA풀이

이분탐색

이진탐색

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

 

코드

---

import java.util.*;

class Solution {
    
    static int [] shipWeights;
    public int shipWithinDays(int[] weights, int days) {
        
        shipWeights=weights;
        
        int left=Arrays.stream(weights).max().orElseThrow(); //최소는 weight에서 가장 큰 원소 
        int right= Arrays.stream(shipWeights).sum(); //weights의 원소 총계
        
        int mid=0;
        int answer=0;
        
        while(left<=right){
            mid=(left+right)/2;
            
            //capacity(mid)에 대한 weight들의 묶음 하나를 패키지라하자. pack는 days와 같아야한다.
            int pack=shipPackage(mid);
            System.out.println(pack);

            //days가 pack 이상이면, mid(capacity)를 작게해야 한다는 것. 
            //최소 capacity를 구해야함. 

            if( days>=pack){
                right=mid-1;
                answer=mid;
            }
            else{
                left=mid+1;
            }
            
            
        }
        
        return answer;
        
    }
    
    public int shipPackage(int capacity){ //주어진 capacity에 대해 weights의 묶음 개수를 구한다. 
        
        int pack=1;
        int sum=0;
        for(int weight: shipWeights){
            if(sum + weight  <= capacity){ //중량의 합이 capacity 이하면 더하기 
                sum+=weight;
            }
            else{
                sum=weight;
                pack++;
            }
        }
        System.out.println(capacity+ " "+ pack);
        return pack;
    }
}

 

 

구해햐하는 것: days에 맞는 capacity의 최소값

-> 이분 탐색을 이용한다. 

left와 right를 정확한 범위를 탐색할 수 있게 설정해야한다. 범위를 벗어나거나 특정 범위를 탐색하게 못한다면 정확도가 떨어질 수 있다. 

 

* capacity의 최소값을 탐색해야하기 때문에 days>=pack일때 (mid가 크다는 뜻으로 더 작게해야함. 최소 capacity에 가까워지는 방향) answer를 mid로 갱신하며 점점 작게하여 최소 capcity를 찾는다. 

* shipPackage함수에서 pack=1인 이유는 처음 묶음을 세준 것이다. 

 

3. 오늘의 회고

---

 

 

• 이분 탐색의 목적(최소값, 최대값)에 따라 찾고자하는 값의 갱신과 left right설정의 고려가 필요하다.
• 어제 이분 탐색 문제를 풀은 경험으로 찾고자 하는 값에 대해 이분 탐색으로 값을 탐색하게 설계했다. 
• 하지만 최소값과 최대값 탐색에서 헷갈려서 막히는 부분이 있었다. 어떤 경우에 answer인지, 그리고 어떤 쪽으로 값을 변화시켜야하는지를 잘 생각하자.