23.02.22. 풀었던 문제들

리트코드 daily challenge - 1011. Capacity To Ship Packages Within D Days

 딱 보고 느꼈다. 어..? ㅋㅋㅋ 이거 어떻게 하지? 면접이라 생각하고 한 5분 고민하다 힌트를 요청했다. 'binary search'... 아, parametric search구나. 생각해 보니 결정 문제로 바꾸어 생각해서 어떤 weight가 주어졌을 때, 그 weight가 days 안에 옮길 수 있는지 없는지는 O(n)으로 아주 쉽게 풀리는 문제다.

 

 wight 최소값은 1이고, 최대값은 25,000,000(weight size 500 * max weight element value 50000)이며, 이러면 O(nlogn)으로 시간 안에 풀리며, lower bound를 찾으면 된다.

 코드를 작성하고 실수가 있었는데, 등호를 넣어야 할 곳에 안 넣고 넣지 말아야 할 곳에 넣은 것이다. 테케르 돌려보고 알았고.. 코테라면 테케를 돌려봐도 되지만 면접 때는 테케를 직접 돌려보고 내는 게 맞는 것 같다.

// rumtime 73ms (beats 43.49%)
// memory 26MB (beats 77.7%)

class Solution {
public:
    // weight에 해당하는 무게를 days 안에 나눌 수 있는지
    bool isCarryable(vector<int>& weights, int weight, int days){
        int weightSize = weights.size(), i = 0;
        // days만큼 순회하면서 weights를 모두 들 수 있는지 검사
        while(days > 0 && i < weightSize){ // 실수 : days >= 0이라고 적음.
            if(weights[i] > weight) return false;

            int dayWeightSum = 0;
            // 더 들 수 있으면 더 듬
            while(i < weightSize && dayWeightSum + weights[i] <= weight){ // 실수 : dayWeightSum + weight[o] < weight라고 적음.
                dayWeightSum += weights[i];
                i++;
            }
            days--; // 날짜 종료
        }
        if(i < weightSize) return false;
        else return true;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int start = 1, end = 25000000;

        while(start < end){
            int mid = start + (end - start) / 2;
            if(isCarryable(weights, mid, days)){ // 옮길 수 있으면 무게를 더 줄여도 됨
                end = mid;
            }
            else start = mid + 1; // 옮길 수 없다면 무게를 늘려야 함.
        }

        return end;
    }
};

 

 자. 그럼 이걸 어떻게 더 개선해야 할까.. 다른 코드들을 살펴봐도, 딱히 코드 내부에서 개선점은 보이지 않는다. isCarryable도 O(n)으로 다 순회하니까... 그럼 결국 이진 탐색의 범위 뿐인 것 같다.

 

// from
int start = 1, end = 25000000;

// to 
// 60ms (beats 70.4%)
int start = *max_element(weights.begin(), weights.end()), end = start * weights.size();

 위와 같이 바꾸었다. start는 최소 'package 중 제일 무거운 무게'여야 하고, end는 'package 중 제일 무거운 무게 * weight size'로 했더니 60ms가 나왔다.

 

 그리고 몇 번 조건을 바꿔 제출하다 실수로 같은 코드를 제출했는데, 같은 코드더라도 실행 결과가 그때그때 조금씩 다르게 나온다. 알아두자!