99클럽 코테 스터디 18일차 TIL - 이진탐색

오늘의 학습 키워드

이진탐색

---

알고리즘 문제

• LeetCode Medium 1011. Capacity To Ship Packages Within D Days
• https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

---

공부한 내용

이진탐색 여러 풀이

---

오늘의 회고

처음 시도

• 여러 개의 데이터가 있고, 주어진 days 안에 모든 데이터를 탐색해서 범위 최솟값을 찾는 문제였기 때문에 이진 탐색으로 범위를 반으로 줄여가며 최솟값을 찾는 알고리즘을 생각했다.
• 먼저 생각한 건 return 값, 초기 범위 최소값(최소 capa), 초기 범위 최댓값(최대 capa)이다.
  • return은 모든 짐(weights)를 정해진 days 안에 모두 나를 수 있는 배 용량의 최솟값이다.
  • 이진 탐색 범위 초기 최솟값 min은 weights 중 가장 큰 수로 최소 capa를 의미한다. 
  • 만약 min이 weights 중 다른 값으로 초기화된다면, weights의 큰 짐을 아예 나를 수 없기 때문에 가장 큰 짐을 최소 capa로 정했다.
  • 이진 탐색 범위 초기 최댓값 max는 모든 짐을 한번에 나를 수 있는 capa로 모든 weights 합으로 초기화했다.
• 여기까진 잘 정했는데 이진 탐색 과정에서 문제가 있었다. 
  • 처음에 문제를 좀 잘 못 이해해서 중간값 mid로 주어진 days와 같은 날짜만큼 모든 짐을 나를 수 있는지에 대해 비교하면서 오류를 범했다. => Case 3번에서 걸림.
  • 또한 if 문으로 비교 로직이 많아지면서 로직이 복잡해졌고, 반복문 안에서 continue;를 남발하게 되었다.

해결

• 탐색 범위를 정했다면, 이제 생각해야 할 것은 중간 값으로 탐색 범위에서 어떻게 범위를 좁힐 수 있을지 고민한다.
• 문제에서 탐색 범위 중간값 mid로 해당 capa가 days 안에 모든 짐을 나를 수 있는지 가능 여부를 판단해야 한다.
  • 해당 capa (mid)로 모든 짐을 나르는 데 걸리는 최소 날짜를 구해서 days보다 크다면 불가능
  • 해당 capa (mid)로 모든 짐을 나르는 데 걸리는 최소 날짜가 days보다 작거나 같다면 가능하다고 판단
• 그 다음으로 가능 여부가 나오면 범위를 어떻게 좁힐 지 결정한다.
  • 해당 capa (mid)로 가능하다면, max = mid - 1로 범위를 좁히면, mid 값은 더 작은 capa으로 설정된다.
  • 해당 capa (mid)로 불가능하다면, min = mid + 1로 범위를 좁히면, mid 값은 더 큰 capa로 설정된다.
  • 이렇게 반복해서 min과 max를 중앙값의 뒤, 앞으로 움직여 중앙값으로 최적 값을 찾아가는 게임이다. 
  • 즉, max를 움직이는 이유는 가능하지만, 더 최적의 값이 있는지를 찾는 것. min을 움직이는 이유는 불가능하기 때문에 가능한 값을 찾는 것이다.

---

문제 풀이

내 풀이

class Solution {
    //return: 모든 짐을 정해진 days 안에 모두 나를 수 있는 배 용량의 최솟값
    int[] weights;
    int days;
    int max;
    int min;
    public void findWeight() {
        int sum = 0;
        int big = weights[0];
        for (int w : weights) {
            sum += w;
            if (w > big) big = w;
        }
        max = sum;
        min = big;
    }

    public boolean canShip(int capa) {
        int sum = 0;
        int count = 1;
        for (int w : weights) {
            sum += w;
            if (sum > capa) {
                count++;
                sum = w;
            }
            if (count > days) return false; 
        }
        return true;
    }

    public int shipWithinDays(int[] weights, int days) {
        this.weights = weights;
        this.days = days;
        findWeight();

        while (min <= max) {
            int mid = (min+max)/2;
            if(canShip(mid)) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return min;
    }
}

 

다른 사람 풀이

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


        int left = 0, right = 0;

        for(int w :  weights)
        {
            left = Math.max(left, w);
            right += w;
        }

        if (days ==1) return right;
        int ans = 0;
       //  System.out.println(left +" left, right" + right);
        while (left < right)
        {
            int mid = (left+right)/2;

            if(canShipPackage(weights, mid, days)){
                right = mid;
                ans = mid;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }

    boolean canShipPackage(int [] weights,int mid,int days)
    {
        int count = 1;
        int sum = 0;
        for(int w: weights)
        {
            if(sum+w > mid)
            {
                sum = 0;
                count++;
            }
            sum += w;

            //System.out.println(count +"," + sum + "," +w);
        }
       // System.out.println(count +"," + mid);


        return count <= days ? true : false;
    }

}