[python3] 2348. Number of Zero-Filled Subarrays

풀이 일자: 23.03.21

난이도: [Medium]

분류: [Array, Math]

문제 내용

문제 내용은 Array 하나 받아서 0으로만 이루어진 subarray가 몇 개 나오는지 리턴하는 문제였다.

 

 

문제 해결 흐름

1. 딱히 생각나는 알고리즘이 없다. 열심히 처음부터 정직하게 탐색해서 0의 위치만 확인하면 되겠다.

→ Linear Search하다가 0이 보이기 시작하면 0에 대한 count를 시작한다. 0이 나오다가 다른 게 나오면 수학적 계산

 

예를 들어,

[0,0,0,0]이 연달아 4번 나왔다고 하자..

[0]인 subgroup이 4개 [0,0]인 subgroup 3개 ..... [0,0,0,0]인 subgroup이 1개.

=> 결과적으로 n개의 0이 연달아 나오는 경우 n(n+1)/2개의 subgroup이 나오는 것을 확인할 수 있다.

 

이를 그대로 코드에 적용시키면,

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0;
        num = 0;

        for i in range(len(nums)):
            if nums[i] != 0:
                ans += (num*(num+1)//2);
                num = 0;
            else:
                num += 1;
                
        if num != 0:
            ans += (num*(num+1)//2);
        return ans;

Time Complexity:  O(N)

시간 복잡도는 주어진 배열에 대한 Linear Search가 이루어지기 때문에 N의 시간복잡도를 가진다.

 

Space Complexity: O(1)

공간복잡도는 어떠한 자료구조를 추가적으로 사용하지 않기 때문에 constant의 공간복잡도를 가진다.

 

 

다른 해결 방식

1.Official Solution

→ 수학적으로 계산할 필요없이 끝에 계산하지 않고 0을 확인함에 따라 더해가는 방식

 

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0;
        num = 0;

        for i in range(len(nums)):
            if nums[i] != 0:
                num = 0;
            else:
                num += 1;
                ans += num;

        return ans;

Time Complexity:  O(N)

시간 복잡도는 주어진 배열에 대한 Linear Search가 이루어지기 때문에 N의 시간복잡도를 가진다.

 

Space Complexity: O(1)

공간복잡도는 어떠한 자료구조를 추가적으로 사용하지 않기 때문에 constant의 공간복잡도를 가진다.

 

 

문제 링크

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

Number of Zero-Filled Subarrays - LeetCode