합이 홀수인 구간 세기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 nums가 주어집니다. 길이가 1 이상인 연속 구간 nums[l..r](0 ≤ l ≤ r < n) 중에서 원소의 합이 홀수인 구간의 개수를 반환하세요.
구간은 시작과 끝 위치로 구별합니다. 값이 같은 구간이라도 위치가 다르면 다른 구간입니다.
입출력 예
| nums | result |
|---|---|
[1, 3, 5] | 4 |
[2, 4, 6] | 0 |
[1, 2, 3, 4, 5, 6, 7] | 16 |
입출력 예 설명
예 1 — 구간은 [1], [3], [5], [1, 3], [3, 5], [1, 3, 5]이고 합은 1, 3, 5, 4, 8, 9입니다. 홀수인 구간은 4개입니다.
예 2 — 짝수만 있으므로 어떤 구간의 합도 홀수가 아닙니다.
예 3 — 28개의 구간 중 16개의 합이 홀수입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(nums: int[]) → long
제한 사항
-
nums.length -
nums[i] - 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(
long)를 사용하세요.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| nums | 기대 출력 |
|---|---|
[1,3,5] | 4 |
[2,4,6] | 0 |
[1,2,3,4,5,6,7] | 16 |
힌트
힌트
누적 합 P[k] = nums[0] + … + nums[k-1](P[0] = 0)을 생각하면 구간 nums[l..r]의 합은 P[r+1] - P[l]입니다.
두 수의 차가 홀수인 것은 두 수의 홀짝이 다를 때뿐입니다. 그러니 실제 합은 필요 없고, 지금까지 나온 누적 합 중 짝수인 것의 개수와 홀수인 것의 개수만 세면 됩니다. 새 누적 합이 홀수이면 지금까지의 짝수 개수만큼, 짝수이면 홀수 개수만큼 답에 더합니다.
음수의 홀짝을 판별할 때 언어에 따라 x % 2가 -1이 될 수 있으니 주의하세요. x & 1을 쓰거나 x % 2 != 0으로 비교하면 안전합니다.
복잡도 목표
모든 구간의 합을 하나씩 확인하면 으로 시간 초과입니다. 누적 합의 홀짝 개수만 세면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1102 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |