[Python 걸음마] LeetCode 1524. Number of Sub-arrays With Odd Sum 문제 풀이

문제

• 링크: https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum/description/
• 입력: 정수 리스트
• 출력: sub-array의 합이 음수인 것의 개수 

 

풀이 방법

• 현재 합이 짝수일 때, 홀수를 더해야 홀수가 되고
• 현재 합이 홀수일 때는 짝수를 더해야 홀수가 된다.
• 예: [1, 3, 5]
  • 짝수가 처음부터 한 개인 이유 -> 0으로 시작하기 때문

	0	1	3	5
지금까지 숫자 합	0	1	4	9
짝수 개수	1	1	2	2
홀수 개수	0	1	2	3
count sum	0	1 (짝수 개수를 더함)	2 (홀수 개수를 더함)	4 (짝수 개수를 더함)
결과				4

 

코드

class Solution(object):

    def numOfSubarrays(self, arr):
        MOD = 10**9 + 7
        even_count = 1
        odd_count = 0
        result = 0
        cur_sum = 0

        for num in arr:
            cur_sum += num
            if cur_sum % 2 == 1:
                result += even_count
                odd_count += 1
            else:
                result += odd_count
                even_count += 1

        result %= MOD
        return result