[leet code] 1524. Number of Sub-arrays With Odd Sum (JAVA)

[leet code] 1524. Number of Sub-arrays With Odd Sum

🗒️알고리즘 분류

#Dynamic Programming #prefix sum #누적합

📌1번째 풀이법: dp

초기값 (i = 0) :

• arr[0]가 짝수라면, dp[0][0]=1, dp[0][1]=0
• arr[0]가 홀수라면, dp[0][0]=0, dp[0][1]=1

전이 (i ≥ 1) :

• arr[i]가 짝수라면,
• 짝수에 짝수를 더하면 짝수, 홀수에 짝수를 더해도 홀수이므로:
  • dp[i][0] = dp[i−1][0]+1
  • dp[i][1] = dp[i−1][1]
  • 여기서 +1 은 단일 원소 부분 배열 arr[i] 가 짝수임을 의미합니다.
• arr[i]가 홀수라면,
• 홀수에 짝수를 더하면 홀수, 홀수에 홀수를 더하면 짝수가 되므로
  • dp[i][0] = dp[i−1][1]
  • dp[i][1] = dp[i−1][0]+1
  • 여기서 +1은 단일 원소 부분 배열 arr[i] 가 홀수임을 의미합니다.

📝 1번째 풀이 코드(JAVA)

class Solution {
    public int numOfSubarrays(int[] arr) {
        int mod = 1_000_000_007;
        int n = arr.length;
        // dp[i][0] : i번째까지 고려할 때, i에서 끝나는 부분 배열 중 짝수 합의 개수
        // dp[i][1] : i번째까지 고려할 때, i에서 끝나는 부분 배열 중 홀수 합의 개수
        int[][] dp = new int[n][2];
        
        // 초기값 설정
        if (arr[0] % 2 == 0) {
            dp[0][0] = 1;
            dp[0][1] = 0;
        } else {
            dp[0][0] = 0;
            dp[0][1] = 1;
        }
        
        int ans = dp[0][1]; // 첫 번째 원소에 대해 홀수이면 더함
        
        // 점화식에 따라 dp 배열 채우기
        for (int i = 1; i < n; i++) {
            if (arr[i] % 2 == 0) {
                // 현재 원소가 짝수: 합의 홀짝이 바뀌지 않음
                dp[i][0] = (dp[i-1][0] + 1) % mod;
                dp[i][1] = dp[i-1][1];
            } else {
                // 현재 원소가 홀수: 홀수와 짝수의 역할이 교환됨
                dp[i][0] = dp[i-1][1];
                dp[i][1] = (dp[i-1][0] + 1) % mod;
            }
            ans = (ans + dp[i][1]) % mod;
        }
        
        return ans;
    }
}

📌2번째 풀이법: prefix sum

• prefix[i]를 arr[0]+arr[1]+⋯+arr[i]로 정의합니다.
• 임의의 부분 배열 arr[i+1…j]의 합은 prefix[j]−prefix[i]입니다.
• 이 차가 홀수가 되려면, prefix[j]와 prefix[i]의 홀짝(parity)이 다르다는 사실을 이용할 수 있습니다.

즉, 홀수 부분 배열의 개수 = (짝수인 prefix sum의 개수 × 홀수인 prefix sum의 개수)

두 prefix의 홀짝이 다르면 해당 부분 배열의 합이 홀수가 됨을 이용하여, 지금까지 등장한 짝수 prefix와 홀수 prefix의 개수를 곱하는 방식(누적합)을 사용합니다.

📝 2번째 풀이 코드(JAVA)

class Solution {
    public int numOfSubarrays(int[] arr) {
        int mod = 1_000_000_007;
        long evenCount = 1;  // 초기 prefix sum 0 (짝수) 한 개
        long oddCount = 0;
        long prefix = 0;
        long ans = 0;
        
        for (int num : arr) {
            prefix += num;
            if (prefix % 2 == 0) {
                // 현재 prefix가 짝수이면, 이전 홀수 prefix와의 차가 홀수임
                ans = (ans + oddCount) % mod;
                evenCount++;
            } else {
                // 현재 prefix가 홀수이면, 이전 짝수 prefix와의 차가 홀수임
                ans = (ans + evenCount) % mod;
                oddCount++;
            }
        }
        
        return (int) ans;
    }
}

⏰총 풀이시간

• 35분