특정 배열 인덱스를 기준으로 왼쪽과 오른쪽에 위치한 짝수(또는 홀수)의 개수가 서로 같은 인덱스를 찾는 것이 이 문제의 핵심입니다. 즉, 어떤 요소를 기준으로 그 왼쪽에 있는 짝수 또는 홀수의 개수와 오른쪽에 있는 짝수 또는 홀수의 개수가 일치하는 지점을 구해야 합니다.
개념을 이해하기 위해 먼저 몇 가지 기본 용어를 살펴보겠습니다.
기본 개념
배열(Array) - 동일한 데이터 타입의 요소들을 담는 자료구조입니다.
배열 인덱스(Array Index) - 배열에서 각 요소의 위치를 나타내는 값입니다. 배열의 인덱스는 항상 0부터 시작합니다.
짝수(Even Number) - 2로 나누어 떨어지는 수입니다.
홀수(Odd Number) - 2로 나누어 떨어지지 않는 수입니다.
모든 정수는 반드시 짝수 또는 홀수 중 하나에 해당합니다.
예제
입력: arr[] = {4, 3, 2, 1, 2}
출력: 2설명
인덱스 2에 위치한 값은 2입니다. 이 값의 왼쪽에는 {4, 3}이 있고, 오른쪽에는 {1, 2}가 있습니다.
- 왼쪽의 짝수 개수: 1개 (4)
- 오른쪽의 짝수 개수: 1개 (2)
또한 왼쪽의 홀수 개수(1개)와 오른쪽의 홀수 개수(1개)도 동일합니다. 따라서 인덱스 2가 조건을 만족하므로 출력 결과는 2가 됩니다.
n개의 정수로 이루어진 배열이 주어졌을 때, 특정 요소의 왼쪽에 있는 짝수 개수와 오른쪽에 있는 짝수 개수가 같거나, 왼쪽에 있는 홀수 개수와 오른쪽에 있는 홀수 개수가 같은 인덱스를 찾아야 합니다. 만약 그러한 조건을 만족하는 인덱스가 존재하지 않으면 -1을 출력하고, 존재한다면 해당 인덱스를 출력하면 됩니다.
알고리즘
양쪽의 짝수 또는 홀수 개수가 동일한 요소의 인덱스를 계산하려면, 기준이 되는 요소의 왼쪽과 오른쪽에 있는 요소들의 개수를 각각 확인해야 합니다.
배열 arr[]와 배열의 요소 개수 n이 주어진 경우 다음 단계를 수행합니다.
Step 1 : i를 0부터 n까지 반복하며 Step 2~5를 수행 Step 2: e_l(왼쪽 짝수), o_l(왼쪽 홀수), e_r(오른쪽 짝수), o_r(오른쪽 홀수)을 0으로 초기화 Step 3: j를 0부터 i-1까지 반복 Step 3.1 : e_l과 o_l 값을 카운트 Step 4: j를 i+1부터 n-1까지 반복 Step 4.1 : e_r과 o_r 값을 카운트 Step 5: (e_l == e_r) 또는 (o_l == o_r)이면 i를 출력
C++ 코드 구현
#include <iostream>
using namespace std;
int main() {
int arr[] = {4, 3, 2, 1, 2};
int n = 5;
cout<<"배열 : ";
for(int i = 0; i < n; i++) {
cout<<arr[i]<<" ";
}
cout<<"\n양쪽의 짝수 또는 홀수 개수가 같은 요소의 인덱스 = ";
for (int i = 0; i < n; i++) {
int o_l = 0, e_l = 0;
int o_r = 0, e_r = 0;
for (int j = 0; j < i; j++) {
if (arr[j] % 2 == 0)
e_l++;
else
o_l++;
}
for (int k = n - 1; k > i; k--) {
if (arr[k] % 2 == 0)
e_r++;
else
o_r++;
}
if (e_r == e_l || o_r == o_l)
cout<<i<<endl;
}
return 0;
}실행 결과
배열 : 4 3 2 1 2 양쪽의 짝수 또는 홀수 개수가 같은 요소의 인덱스 = 2
이 알고리즘의 시간 복잡도는 O(n²)입니다. 각 인덱스마다 왼쪽과 오른쪽을 모두 순회하기 때문입니다. 만약 성능 최적화가 필요하다면, 누적합(prefix sum) 방식을 활용하여 한 번의 순회로 전체 배열의 짝수·홀수 누적 개수를 미리 계산한 후 비교하면 O(n)으로 개선할 수 있습니다.