양의 정수로 이루어진 배열이 주어졌을 때, 각 부분 배열(subarray) 안에 포함된 짝수와 홀수의 개수가 서로 같은 경우를 모두 찾아야 합니다. 예를 들어 배열이 { 1, 2, 3, 4 }라면 조건을 만족하는 부분 배열은 { 1, 2 }, { 2, 3 }, { 3, 4 }, { 1, 2, 3, 4 }이며, 그 개수는 4개입니다.
예시를 통해 자세히 살펴보겠습니다.
입력 − arr[] = {1, 3, 5, 7, 8, 3, 2}
출력 − 짝수와 홀수 개수가 같은 부분 배열의 수 − 4
설명 − 해당 부분 배열은 { 7, 8 }, { 8, 3 }, { 3, 2 }, { 7, 8, 3, 2 }
입력 − arr[] = {2, 4, 6}
출력 − 짝수와 홀수 개수가 같은 부분 배열의 수 − 0
설명 − 모든 요소가 짝수이므로 조건을 만족하는 부분 배열이 하나도 없습니다.
알고리즘 접근 방식
이 방식에서는 변수 temp를 배열 요소들의 누적 차이(초기값 0)로 사용합니다. arr[i]가 홀수이면 temp를 1 증가시키고, 짝수이면 1 감소시킵니다. temp 값이 반복해서 나타난다면, 그 두 인덱스 사이에는 짝수와 홀수의 개수가 동일한 부분 배열이 반드시 존재한다는 뜻입니다. temp는 양수가 될 수도 있고 음수가 될 수도 있으므로, 양수 차이의 빈도를 저장하는 해시 배열 arr_1[size+1]과 음수 차이의 빈도를 저장하는 arr_2[size+1], 두 개의 배열을 사용합니다.
차이가 temp < 0인 경우에는 arr_2[-temp]의 빈도를 count에 더합니다. [-(-temp)] 연산으로 음수 차이를 양수 인덱스로 변환할 수 있습니다.
temp > 0인 경우에는 arr_1[temp]의 빈도를 count에 더합니다. 동일한 차이 값이 나타난 모든 지점은 곧 부분 배열의 일부가 되며, 매번 해당 빈도 값을 1씩 갱신해 줍니다.
Arr[] = { 1, 3, 5, 7, 8, 3, 2 }0부터 시작하는 temp 값의 변화 −
1, 2, 3, 4, 3, 4, 3
arr_1[] = { 1, 1, 1, 3, 2, 0, 0, 0 } // 모든 차이가 양수
arr_2[] = { 0, 0, 0, 0, 0, 0, 0, 0 } // 음수인 차이 없음
매 반복마다 arr_1[temp]를 count에 더하면 count = 4
찾은 부분 배열 − { 7, 8 }, { 8, 3 }, { 3, 2 }, { 7, 8, 3, 2 }
초기 배열을 arr[]로 선언합니다.
Sub_even_odd(int arr[], int size) 함수는 배열과 그 길이를 받아 짝수와 홀수 개수가 같은 부분 배열의 개수를 반환합니다.
count를 0으로 초기화하고, 홀수를 만나면 증가하고 짝수를 만나면 감소하는 변수 temp를 준비합니다.
temp의 빈도를 저장할 두 배열 arr_1[]과 arr_2[]를 사용합니다. arr_1[]은 temp가 양수인 경우(배열 전체가 짝수로만 이루어진 경우 최대 size+1까지 가능)를, arr_2[]는 temp가 음수인 경우를 저장합니다.
for 루프를 사용해 arr[]를 순회합니다.
(arr[i] & 1) == 1이면 arr[i]는 홀수이므로 temp를 증가시키고, 그렇지 않으면 감소시킵니다.
temp < 0이면 arr_2[]에서 해당 빈도를 count에 더하고, 그 빈도를 1 증가시킵니다.
temp > 0이면 arr_1[]에서 해당 빈도를 count에 더하고, 그 빈도를 1 증가시킵니다.
최종적으로 count는 arr[]에서 짝수와 홀수 개수가 같은 부분 배열의 총 개수입니다.
count를 결과로 반환합니다.
예제
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++){
if((arr[i] & 1) == 1)
{ temp++; }
else
{ temp--; }
if (temp < 0){
count += arr_2[-temp];
arr_2[-temp]++;
}
else{
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main(){
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"짝수와 홀수 개수가 같은 부분 배열의 수: "<<Sub_even_odd(arr, size);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
짝수와 홀수 개수가 같은 부분 배열의 수: 4