정수로 이루어진 배열 Arr[]가 주어졌을 때, 요소들의 합이 짝수가 되는 가장 긴 부분 배열(subarray)의 길이를 구하는 것이 목표입니다. 즉, 부분 배열 안 요소들의 합이 짝수이면서 길이가 최대가 되는 경우를 찾는 문제입니다.
예제 입력 및 출력
입력 − Arr[] = { 2, 3, 5, 2, 6, 7 }
출력 − 부분 배열의 최대 길이: 4
설명 − 가장 긴 부분 배열은 { 5, 2, 6, 7 }이며, 합은 20으로 짝수입니다.
입력 − Arr[] = { 5, 7, 7, 3, 4 }
출력 − 부분 배열의 최대 길이: 4
설명 − 가장 긴 부분 배열은 { 5, 7, 7, 3 }이며, 합은 22로 짝수입니다.
해결 접근 방식
이 문제를 해결하기 위해 아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 정수 배열 Arr[]에 정수 값들을 저장합니다.
- 변수 size는 배열의 길이를 저장하는 데 사용됩니다.
- 함수 Length(int arr[])는 배열의 합이 짝수인지 확인하고, 변수 leng은 부분 배열의 길이를 저장합니다.
- 먼저 배열 전체의 합을 계산하여, 이미 짝수라면 배열의 길이 n을 그대로 반환합니다.
- 합이 홀수라면, 첫 번째 요소부터 배열 전체를 순회하면서 홀수 요소를 찾습니다. 홀수 요소(arr[i])를 발견하면 해당 요소를 제외했을 때 좌우 두 구간 중 더 긴 쪽의 길이를 계산합니다.
- 모든 경우를 비교하여 가장 긴 부분 배열의 길이를 반환합니다.
핵심 아이디어는 간단합니다. 배열 전체의 합이 홀수라면, 합을 짝수로 만들기 위해서는 반드시 홀수 요소 하나를 범위에서 배제해야 합니다. 따라서 각 홀수 요소를 기준으로 왼쪽 구간과 오른쪽 구간의 길이를 비교하여 더 긴 쪽을 후보로 삼으면, 자연스럽게 최적의 답을 얻을 수 있습니다.
C++ 코드 예제
#include <iostream>
int Length(int arr[], int n){
int sum = 0, leng = 0;
// 배열 전체의 합이 짝수인지 먼저 확인
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 == 0) // 전체 합이 이미 짝수인 경우
return n;
// arr[i]가 홀수인 인덱스 i를 찾아
// 해당 요소를 제외한 좌우 구간의 길이를 비교하여
// 최대 길이 부분 배열을 구함
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 1)
leng = i > n - i - 1 ? i : n - i - 1;
}
return leng;
}
int main(){
int Arr[] = { 1, 2, 6, 2, 4, 2 };
int size = 6;
printf("부분 배열의 합이 짝수일 때의 최대 길이: %d", Length(Arr, size));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
부분 배열의 합이 짝수일 때의 최대 길이 : 5
예제 배열 { 1, 2, 6, 2, 4, 2 }의 전체 합은 17로 홀수입니다. 유일한 홀수 요소인 맨 앞의 1을 제외한 { 2, 6, 2, 4, 2 }의 합은 16으로 짝수이므로, 최대 길이는 5가 됩니다.
복잡도 분석
배열을 최대 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열의 크기가 커져도 효율적으로 동작하는 선형 시간 알고리즘입니다.