[코딩테스트 일지 - 99클럽] 14일차 - Capacity To Ship Packages Within D Days

코딩테스트 항해99 클럽 - 14일차

Jun 12

7 min read

코딩 테스트 준비 일지 14 일차

응시 사이트 : LeetCode
문제 : Capacity To Ship Packages Within D Days
난이도 : 중상
풀이시간 : 1h 39m

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Constraints:

1 <= days <= weights.length <= 5 * 104
1 <= weights[i] <= 500

문제 풀이 접근

이 문제 풀이는 단번에 접근할 수 없었다. 이분탐색 개념도 희미해져서 잘 몰랐을 뿐더러, 풀면서 이분탐색이 뭐였지? 하면서 개념을 다시 살펴보고 문제를 다시확인했다.
처음 설정한 방향성은 List 를 하나 더만들어서 [1,2,3,4,5,6,7,8,9,10]이 있다면, 이분 탐색으로 중간지점 인덱스 5, value 6 이하의 값을 1,2,3,4,5 해서 선적에 넣고 리스트 앞에서 다 날리고 이후에 [6,7,8,9,10] 에서 또 중간지점 인덱스 2 , value 8 이하의 점을 날리고 [8,9,10] 에서 8 날리고 9 날리고 10 날리고 하면 딱 될것 같아서 생각을 해봤으나, 3번의 예시가 보기좋게 응 아니야라는 메시지를 날렸다.

결국 혼자 풀지못하고 풀이 영상을 확인하니 그제서야 접근 방식을 알았다. 방식은 인덱스로 이분탐색하면 안되는 것이 핵심이었다.
1. 무게 중 가장 큰 값이 Left 로 들어가고, 모든 무게의 합이 Right 로 들어간다 .
2. 여기서 조건에 따라 양 사이드를 땡기는 투포인터 느낌으로다가 L = mid + 1, R = mid -1 로 범위를 당겨온다.
3. 조건은 CalcDays >= days 일 경우, Low = mid + 1 을 한다. ( 이 경우, 선적의 중량이 부족하다는 소리, 그래서 결국 몇일 더걸린다는 얘기니까 Low 를 땡겨서 선적의 중량을 올린다.)
반대 조건인 else 구문은 High = mid - 1 을 한다. ( 중량이 차고 넘치니까, 예산일정보다 빨리 끝난다는 얘기다. 그러니, 선적의 중량을 낮춘다.)

예시 풀이

2번이 테스트 하면서 잘 안됐었어서 2번으로 예시 풀이 하겠다.

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

이 중 가장 큰 값인 4, 를 Left, 모든 합 16 을 Right , mid 값은 이 중간 값 ( m 은 여기서 선적 용량 )
L = 4 , R = 16 , M = 10
M = 10 일때, CalcDays [3,2,2] , [4,1,4] => 2로 끝난다. 선적의 중량이 많다. 낮춘다.
R = M - 1 로 변경
L = 4, R = 9 , M = 6
M = 6 일때, CalcDays [3,2] [2,4] [1,4] => 3그룹 이지만 실제 CalcDays 는 2 이다.
당긴다. R = 6 - 1 = 5
L = 4 , R = 5 , M = 5
M = 5 일때, CalcDays [3,2] [2] [4] [3,1] => 4, CalcDays > Days
L = 5 + 1 로 놓는다.

While ( Left <= Right ) 의 조건으로 빠져나와 Left를 반환하면 최적의 값을 출력할 수 있다.

작성 코드

using System.Collections.Generic;
public class Solution {
public int ShipWithinDays(int[] weights, int days) {    int low = 0;
    int high = 0;
    int mid = 0;

    for(int i = 0; i &lt; weights.Length; ++i)
    {
        high += weights[i];
        low = Math.Max(low, weights[i]);
    }

    // 용량을 기준으로 BS 한다.
    // 예시 1번으로는, [10, 55] 로 BS 진행한다.
    

    while(low &lt;= high)
    {
        int calcDays = 0; // 산정된 일 수 
        int nowSum = 0;

        mid = (low + high) / 2; // 용량

        for(int i = 0; i &lt; weights.Length; ++i)
        {
            if(nowSum + weights[i] &gt; mid)
            {
                // 현재 용량 선적보다 많다. 일 수를 추가해야함.
                nowSum =0;
                ++calcDays;
            }

            nowSum += weights[i];
        }

        // 여기서 용량 선적이 남으면, 다시 최적을 찾는다. 
        if(calcDays &gt;= days)
            low = mid + 1;
        else 
            high = mid - 1;
    }

    return low;
}}

코드 결과