C++로 배열에서 연속된 짝수의 최대 개수 찾기

문제 소개

크기가 n인 배열 A가 주어졌을 때, 배열 안에서 연속된 짝수의 최대 개수를 찾는 것이 목표입니다.

예를 들어 배열이 다음과 같다고 해보겠습니다.

A = [1, 2, 3, 4, 6, 8, 7]

이 경우 인덱스 3부터 5까지의 값인 4, 6, 8이 연속된 짝수 세 개에 해당하므로, 정답은 3이 됩니다.

접근 방법

이 문제는 선형 탐색 한 번으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 두 개의 카운트 변수를 사용하는 것입니다.

• max_current: 현재 이어지고 있는 연속 짝수의 개수
• max_till_now: 지금까지 발견한 연속 짝수의 최대 개수

배열을 순회하면서 짝수를 만나면 max_current를 1 증가시키고, 이 값을 max_till_now와 비교하여 더 큰 값으로 갱신합니다. 반대로 홀수를 만나면 연속성이 끊긴 것이므로 max_current를 0으로 초기화합니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리는 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int maxEvenContiguous(int arr[], int n) {
    int max_current = 0, max_till_now = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0)
            max_current = 0;   // 홀수를 만나면 연속 카운트 초기화
        else {
            max_current++;     // 짝수면 카운트 증가
            max_till_now = max(max_current, max_till_now);
        }
    }
    return max_till_now;
}

int main() {
    int arr[] = {1, 2, 3, 4, 6, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max contiguous even number count: " << maxEvenContiguous(arr, n);
}

실행 결과

Max contiguous even number count: 3

동작 과정 살펴보기

배열 [1, 2, 3, 4, 6, 8, 7]을 단계별로 확인해 보면 다음과 같습니다.

• 1 (홀수) → max_current = 0
• 2 (짝수) → max_current = 1, max_till_now = 1
• 3 (홀수) → max_current = 0
• 4 (짝수) → max_current = 1, max_till_now = 1
• 6 (짝수) → max_current = 2, max_till_now = 2
• 8 (짝수) → max_current = 3, max_till_now = 3
• 7 (홀수) → max_current = 0

최종적으로 max_till_now에는 3이 저장되어 반환됩니다.

마무리

이 문제는 슬라이딩 윈도우나 누적 카운팅 기법의 기본적인 형태로, 코딩 테스트에서 자주 등장하는 유형입니다. 같은 원리를 응용하면 '최장 연속 1의 개수', '최장 증가 부분 구간 길이' 등 다양한 변형 문제에도 쉽게 적용할 수 있습니다.