(Leet Cods JS)2348. Number of Zero-Filled Subarrays

https://leetcode.com/problems/number-of-zero-filled-subarrays/

Number of Zero-Filled Subarrays - LeetCode

const zeroFilledSubarray = function(nums) {
    const arr = Array.from({length: 100001}, () => 0);
    const zeros = [];
    let answer = 0;
    let isContinuous = false;
    let count = 0;

    arr[1] = 1;

    for(let i = 1; i < 100001; i++) {
        arr[i] = arr[i - 1] + i;
    }

    for(let i = 0; i < nums.length; i++) {
        if(nums[i] === 0) {
            count++;

            if(!isContinuous) {
                isContinuous = true;
            }
        } else {
            if(isContinuous) {
                zeros.push(count);
            }
            count = 0;
            isContinuous = false;
        }
    }

    if(isContinuous) {
        zeros.push(count);
    }

    for(let i = 0; i < zeros.length; i++) {
        answer += arr[zeros[i]];
    }

    return answer;
};

연속적인 0의 subarray의 길이를 구하면 된다.

 

sub-array를 구할 때에는 규칙이 발생한다.

0 : 1개

0 0 : 3개

0 0 0 : 6개

0 0 0 0 : 10개

...

즉, i = 1이고 0의 개수라 하고, x(i)가 0을 i개 가진 배열의 sub-array의 개수라고 할 때,

x(1) = 1

x(2) = 3

x(3) = 6

x(4) = 10

이라는 규칙으로 정의할 수 있다.

x(i) = i + x(i - 1) 이라는 규칙이 발생한다.

 

그렇기 때문에 arr라는 배열에 이 규칙대로 0의 개수에 따른 sub-array의 개수를 미리 넣어둔다.

그리고 nums를 순회하면서 연속적인 0의 개수를 zeros라는 배열에 저장한다.

연속적인 것을 의미하는 isContinuous 라는 flag로 확인하며,

nums의 순회가 끝나면 마지막에 flag를 확인해서 남아있는 0의 sub-array 까지 확인한다.

 

이후 zeros를 순회해서 미리 저장해놓은 sub-array 개수를 확인해서 answer를 늘려주면 된다.