[Python] LeetCode - 2348. Number of Zero-Filled Subarrays

LeetCode 2348번 Number of Zero-Filled Subarrays 문제는 배열에 존재하는 0으로 된 부분배열을 구하는 문제다. 난이도는 Medium이다.

 

리트코드 2348번 Number of Zero-Filled Subarrays 문제 정보

알고리즘 분류

- Greedy

난이도

- Medium

 

문제 요약

• 정수로된 배열 nums가 주어졌을 때, 0으로 된 subarray의 개수를 구하라.

 

문제 풀이 과정

• 선형탐색 하면서 0이 몇개씩 이어져있는지 확인한다.
  • 0 N개로 이루어진 배열의 subarray는 총 N(N+1)/2개이다.

코드

class Solution:

    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        zero_cnt = 0

        def get_subarray_cnt(size):
            return (size * (size + 1)) // 2
        
        for num in nums:
            if num == 0:
                zero_cnt += 1
            else:
                ans += get_subarray_cnt(zero_cnt)
                zero_cnt = 0
        
        ans += get_subarray_cnt(zero_cnt)
        return ans

• 시간복잡도: O(N)
• 공간복잡도: O(1)