[C] LeetCode 1712. Ways to Split Array Into Three Subarrays

문제

번역

정수 배열을 나눈게 good 이려면:

3개의 비어있지 않은 부분 배열로 나눈걸 왼쪽부터 순서대로 left, mid, right이라 하자.

left의 합은 mid보다 작거나 같아야 하고, mid의 합은 right보다 작거나 같아야 한다.

음수가 아닌 정수 배열 nums가 주어졌을때, nums배열을 good 하게 나눈 개수를 반환해라.

이때, 수가 너무 클 수 있으니 \( mod\)   \(   10^9 + 7\)을 해서 반환해라.

접근 방법 및 소스 코드

일단 각 부분 배열들의 합을 쉽게 구할 수 있는 방법이 있을까 생각하다가 누적합 기법이 생각났다.

누적합 기법은 각 원소를 누적하여 더해둔 배열을 이용하여 구간의 합을 O(1) 만에 구할 수 있는 방법이다.

 

먼저 누적합 배열을 만들었다. 그 이후 배열을 3개로 나누기 위해 rmin과 rmax 변수를 사용했다.

rmin=1이라고 하자. 그러면 0번부터 rmin까지의 합 <= rmin부터 rmax까지의 합 <= rmax부터 n-1까지의 합 이 조건을 만족할때까지 rmax를 계속해서 늘려가면 된다.

그리고 해당 조건을 최대한 만족하는 가장 큰 rmax를 구했다 하자.

그럼 rmin=1 일때 rmax - rmin 만큼의 good 부분배열이 있는 것이다.

 

int waysToSplit(int* nums, int numsSize) {
    int rmin = 1, rmax=1;
    int* sum = (int *)malloc(sizeof(int) * numsSize);
    *(sum + 0) = nums[0];
    int counter = 0;
    for(int i = 1; i < numsSize; i++) *(sum + i) =  *(sum + i - 1) + nums[i];
    for(int i =0;i<numsSize-2;i++) {
        if(rmin <= i) rmin = i+1;
        while(rmin < numsSize -1 && *(sum + i) > *(sum + rmin) - *(sum + i)) rmin++;
        if(rmin > rmax) rmax = rmin;
        while(rmax < numsSize-1 && *(sum + rmax) - *(sum + i) <= *(sum+numsSize-1) - *(sum + rmax)) rmax++;
        counter = ( counter + rmax - rmin ) % 1000000007;
    }
    free(sum);
    return counter;
}

 

 

나름 나쁘지 않은 결과를 얻은 것 같다.

시간복잡도와 공간복잡도 모두 O(n)이다.