Python으로 합이 홀수인 부분 배열 개수 구하기 (접두사 합 활용)

문제 이해하기

배열 arr가 주어졌을 때, 원소들의 합이 홀수가 되는 부분 배열(연속된 하위 배열)의 개수를 구하는 문제입니다. 만약 답이 너무 커진다면 결과를 10^9+7로 나눈 나머지를 반환하면 됩니다.

예를 들어 입력이 arr = [8,3,7]이라고 가정해 보겠습니다. 만들 수 있는 모든 부분 배열은 [[8], [3], [7], [8,3], [3,7], [8,3,7]]의 여섯 가지이며, 각각의 합은 순서대로 [8, 3, 7, 11, 10, 18]입니다. 이 중 합이 홀수인 경우는 3, 7, 11의 세 가지이므로 정답은 3이 됩니다.

접근 방법: 접두사 합(Prefix Sum)과 홀짝성

모든 부분 배열을 일일이 확인하는 브루트 포스 방식은 O(n²) 이상의 시간이 걸립니다. 하지만 접두사 합과 홀짝성(패리티)을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 두 접두사 합의 홀짝성이 서로 다르다면, 그 사이에 해당하는 부분 배열의 합은 반드시 홀수가 됩니다. 따라서 각 위치에서 지금까지 등장한 '반대 홀짝성' 접두사 합의 개수를 더해주면 됩니다.

알고리즘 단계

freq를 [1, 0]으로 초기화합니다. (빈 접두사의 합은 0, 즉 짝수이므로 짝수 개수를 1로 시작합니다.)
ans(정답 개수)와 prefix(접두사 합)를 0으로 초기화합니다.
배열의 각 원소 x에 대해 다음을 수행합니다:
- prefix에 x를 더합니다.
- 현재 접두사 합과 홀짝성이 반대인 접두사 합의 개수, 즉 freq[1 ^ (prefix & 1)]를 ans에 더합니다.
- freq[prefix & 1] 값을 1 증가시켜 현재 홀짝성을 기록합니다.
모든 원소를 처리한 후 ans를 10^9+7로 나눈 나머지를 반환합니다.

구현 예제

def solve(arr):
    freq = [1, 0]
    ans = prefix = 0
    for x in arr:
        prefix += x
        ans += freq[1 ^ (prefix & 1)]
        freq[prefix & 1] += 1
    return ans % (10**9+7)

arr = [8,3,7]
print(solve(arr))

입력

[8,3,7]

출력

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 크기가 고정된 빈도 리스트 하나만 사용합니다.

이처럼 접두사 합의 홀짝성만 추적하면, 부분 배열의 합을 매번 새로 계산하지 않고도 합이 홀수인 부분 배열의 개수를 선형 시간에 정확히 구할 수 있습니다.