Leetcode 2348. Number of Zero-Filled Subarrays with Python

문제

Given an integer array nums, return the number of subarrays filled with 0.

A subarray is a contiguous non-empty sequence of elements within an array.

정수 배열이 주어집니다, 배열에서 찾을수 있는 0으로만 채워진 부분 배열의 갯수를 리턴하세요.

예시

Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation: [0, 0] 과 [0, 0] 이 0으로만 채워진 부분이며, 이들의 0으로만 채워진 부분배열은 각각 3개로 총 6개의 부분배열이 있다.

제한

• $1 <= nums.length <= 10^5$
• $-10^9 <= nums[i] <= 10^9$

풀이법

생각보다 매우 간단해서 놀랐다.

1. dp?

• 일단 든 생각은 특정 길이의 0으로만 이루어진 배열이 가질수 있는 모든 부분 배열의 갯수를 빠르게 구하는 일이였다.
• 만약 직접 하나하나 찾는다면 $O(N^2)$의 시간복잡도를 가지기에, 제일 긴 길이가 10000개가 되어 시간안에 해결이 불가능했다.

2. O(1)

• 근데 다시 보니 규칙이 보였다

[0]

• 한개의 0으로만 이루어져 자기자신인 1개
• 1

[0, 0]

• [0] 두개와 [0, 0] 총 3개
• 1 + 2

[0, 0, 0]

• [0] 세개와 [0, 0] 두개와 [0, 0, 0] 한개로 총 6개
• 1 + 2 + 3

여기서 주목해야하는 사실은 결과가 그냥 1~n의 합과 같게 된다는 것이다!

그냥 0의 긴 부분배열의 길이들을 찾아서 (n * (n+1)) / 2 공식을 사용해 더해주면 그만이다..

Medium 난이도이길래 이번엔 어떤식으로 조금 꼬아놨을까 했는데 너무 허무하다

from typing import List


class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        cnt = 0
        for v in nums:
            if v == 0:
                cnt += 1
            else:
                ans += (cnt * (cnt+1)) // 2
                cnt = 0
        return ans + (cnt * (cnt+1)) // 2

사실 처음 제출할땐 O(logN)의 시간복잡도를 가진 방법이 있어서 내 방식이 한 중간이나 중간 이하의 시간으로 나올줄 알았는데

최상위길래 깜놀..