Number of Zero-Filled Subarrays(leetcode, 2348)

문제 설명

배열이 주어지는 데, 이때 0으로만 이루어진 배열의 갯수를 구하는 문제다. 여기에서 0의 순서는 바뀌면 안 된다.

문제 풀이

첫 번째 접근

처음에는 컴비네이션을 생각했다.
0이 만일 총 3개가 뭉쳐 있다면 3C1 + 3C2 + 3C3 이렇게... 왜 그렇게 어렵게 가십니까? 그러기 위해서 팩토리얼을 dp로 구현하고 이미 구한 값을 계산하는 방식을 이용했다.
그러나 여기서 중요한 실수가 발생했는데, 0의 하위배열은 순서를 바꾸면 안 된다는 것이다.

예를 들어 0이 세 개 있다면 3C2는 첫 번째 0과 두 번째 0, 두 번째 0과 세 번째 0, 첫 번째 0과 세 번째 0이렇게 조합이 된다. 우리는 0의 순서를 바꾸면 안 되기에 마지막 순서인 첫 번째 0과 세 번쩨 0을 포함하면 안 된다.

그렇기에 자꾸만 숫자가 하나더 늘어서 나오는 것이었다. 이걸 어떻게 해결하느냐? 방법은 너무 간단해 눈물이 날 지경이었다.

두 번째 접근

하위 배열의 갯수를 구하기 위해 그냥 더하면 된다. 0이 세 개라고 하면 0을 하나씩, 두 개씩, 세 개씩 해서 3+2+1이 된다. 조합이니 뭐니 생각할 필요가 없는 문제였다...

공통 접근

0의 갯수를 세주기 위해서 left와 right를 정하고 right에서 left를 빼고 1을 더하는 방식을 이용했다. 그러나 그냥... 0을 일일이 세 주면 된다. 어... 응...

코드

class Solution {

    public static long answer;
    public static long[] dp;

    public long zeroFilledSubarray(int[] nums) {
        int left = 0;
        int right = 0;
        answer = 0;

        for(int i=0; i<nums.length; i++){
            //새로운 0의 시작
            if(nums[i] == 0 && right == 0){
                left = (i+1);
            }

            if(nums[i] == 0 && left != 0){
                right = (i+1);
                if(i != nums.length-1 && nums[i+1] != 0){
                    sumArray(left, right);
                }
            }

            if(nums[i] != 0){
                right = 0;
                left = 0;
            }

        }

        if(left != 0 && right != 0){
            sumArray(left, right);
        }

         return answer;
    }

    public void sumArray(int left, int right){

        int zero = right - left + 1;
        long tmp = 0;

        for(int i=zero; i>0; i--){
            tmp += i;
        }
        answer += tmp;
        }

        tmp += 1;

        System.out.println(tmp);

        answer += tmp;*/



    }

내가 짠 팩토리얼 dp 코드

    public static void factorial(int zero){

        for(int i=1; i<=zero; i++){
            long tmp = 1;
            for(int j=1; j<=i; j++){
                tmp *= j;
            }
            dp[i] = tmp;
        }

    }

이건 조합

        for(int i=1; i<zero; i++){
            tmp += (dp[zero]/(dp[i]*dp[zero-i]));
            //System.out.println(tmp);
        }