C++로 정확히 k개의 홀수를 포함하는 가장 긴 부분 배열 찾기

이번 글에서는 n개의 요소를 가진 배열에서 정확히 k개의 홀수를 포함하는 가장 긴 부분 배열(sub-array)의 길이를 찾는 방법을 알아보겠습니다.

예를 들어 배열 A = [2, 3, 4, 11, 4, 12, 7]이고 k = 1이라면, 정답은 4가 됩니다. 이때 해당 부분 배열은 [4, 11, 4, 12]입니다.

해결 접근 방식: 슬라이딩 윈도우(Sliding Window)

이 문제는 슬라이딩 윈도우 기법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• max := 0, count := 0, start := 0으로 초기화합니다.
• i를 0부터 n-1까지 순회하며 다음을 수행합니다.
  • arr[i]가 홀수라면 count를 1 증가시킵니다.
  • count > k인 동안(start <= i 조건 유지) 윈도우의 왼쪽 끝을 축소합니다.
    • arr[start]가 홀수라면 count를 1 감소시킵니다.
    • start를 1 증가시킵니다.
  • count == k라면 현재 윈도우 길이(i - start + 1)가 max보다 클 경우 max를 갱신합니다.
• 순회가 끝나면 max를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다. 각 요소는 최대 두 번(윈도우 확장 시 한 번, 축소 시 한 번)만 처리되기 때문입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int oddSubarrayMaxLength(int arr[], int n, int k) {
    int max_len = 0, count = 0, start = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0)
            count++;
        while (count > k && start <= i)
            if (arr[start++] % 2 != 0)
                count--;
        if (count == k)
            if (max_len < (i - start + 1))
                max_len = i - start + 1;
    }
    return max_len;
}

int main() {
    int arr[] = {2, 3, 4, 11, 4, 12, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 1;
    cout << "Maximum Length is: " << oddSubarrayMaxLength(arr, n, k);
}

실행 결과

Maximum Length is: 4

동작 과정 살펴보기

예제 배열 [2, 3, 4, 11, 4, 12, 7]에서 k = 1일 때의 진행 과정을 단계별로 보면 다음과 같습니다.

• i = 0 (2): 짝수이므로 count = 0. count == k가 아니므로 갱신 없음.
• i = 1 (3): 홀수이므로 count = 1. 윈도우 [2, 3], 길이 2 → max = 2.
• i = 2 (4): 짝수이므로 count = 1. 윈도우 [2, 3, 4], 길이 3 → max = 3.
• i = 3 (11): 홀수이므로 count = 2 > k. start를 이동해 2, 3을 제거 → count = 1. 윈도우 [4, 11], 길이 2 → max 유지.
• i = 4 (4): 짝수이므로 count = 1. 윈도우 [4, 11, 4], 길이 3 → max 유지.
• i = 5 (12): 짝수이므로 count = 1. 윈도우 [4, 11, 4, 12], 길이 4 → max = 4.
• i = 6 (7): 홀수이므로 count = 2 > k. start를 이동해 4, 11을 제거 → count = 1. 윈도우 [4, 12, 7], 길이 3 → max 유지.

최종 결과로 4가 출력되며, 이는 [4, 11, 4, 12]라는 가장 긴 부분 배열에 해당합니다.