[LeetCode] 410. Split Array Largest Sum

https://leetcode.com/problems/split-array-largest-sum/description/

Split Array Largest Sum - LeetCode

 

 

 

문제정의

1. nums라는 배열과 정수 k가 주어진다.

2. nums 배열을 비어있지 않은 k개의 연속된 부분 배열로 나누어야하며 각각 부분 배열의 합 중에서 가장 큰 값이 최소가 되어야함

3. 그렇게 분할했을때 나오는 가장 작은 최대 부분 배열의 합을 반환해라

 

배열의 길이는 최대 1000이다.

 

문제를 먼저 보고 가장 먼저 든 생각은 부분 배열에서 가장 큰 값을 작게 해야 하니 부분 배열을 만들때 임기점을 찾으면 바로 구할 수 있지 않을까 생각해서 이분탐색을 사용하여 구현하였다.

 

먼저 가장 중요한 탐색 지점인데 처음에 버릇처럼 lo, hi를 잡을때 1, 10^9 으로 잡았다가 중간 테케에서 틀렸다.

 

배열에서 가장 큰 값이 lo가 될것이며 모두 더한 값이 hi가 될 것이다.

 

예를 들어서 [1, 3, 3] 이고, k = 3 이라고 가정하면

 

1, 3, 3 으로 나눌 수 있고 이때 가장 큰 부분배열의 최소를 구한다고 하면 당연히 3이 될것이다.

 

이처럼 탐색 범위를 lo는 가장 큰 값, hi는 모든 배열을 합한 값으로 설정할 수 있다.

 

        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;        // 분할했을때 한계(최댓값)

            int split = 1;
            int value = 0;

            for(int i = 0; i < nums.size(); i++) {
                if(value + nums[i] > mid) {
                    split++;
                    value = nums[i];
                }
                else value += nums[i];
            }

            if(split > k) {
                lo = mid;
            }
            else hi = mid;

 

가장 핵심이 되는 부분으로 mid를 구하고 for문을 돌며 부분 배열의 임계점을 기준으로 몇개의 부분조각이 나오는지 구하는 방식이다.

 

만약 부분배열이 k이상 나온다면 k만큼 맞춰야 하기에 lo를 mid로 당겨 임계점을 높이 설정하며 아닌경우(k랑 같거나 작은 경우) 임계점을 높게 설정했기에 hi를 mid로 땡겨서 더 작은 부분에서 탐색하도록 설정하였다.

 

전체코드

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int sum = 0;
        int val = 0;

        for(auto &iter : nums) {
            val = max(iter, val);
            sum += iter;
        }

        int lo = val - 1;
        int hi = sum;

        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;        // 분할했을때 한계(최댓값)

            int split = 1;
            int value = 0;

            for(int i = 0; i < nums.size(); i++) {
                if(value + nums[i] > mid) {
                    split++;
                    value = nums[i];
                }
                else value += nums[i];
            }

            if(split > k) {
                lo = mid;
            }
            else hi = mid;
        }

        return lo + 1;
    }
};

 

회고록

처음 부분배열의 개수를 계산할때 0으로 설정하고 배열을 순회하며 더하다가 임계점보다 크거나 같은 경우를 엄격하게 설정해서 테케를 틀렸었다 -> 누적된 합이 임계점보다 크면 그냥 잘라주고 나머지를 더해서 해결하였음, 또한 split 변수를 마지막에 더하지 않고 처음부터 1로 설정해서 해결하였다.