C++ 배열에서 좌우 짝수·홀수 개수가 같은 인덱스 찾기

문제 소개

n개의 원소를 가진 배열이 하나 주어졌다고 가정해 봅시다. 우리가 찾아야 하는 것은 특정 인덱스로, 그 인덱스를 기준으로 왼쪽에 있는 짝수의 개수와 오른쪽에 있는 짝수의 개수가 같거나, 왼쪽에 있는 홀수의 개수와 오른쪽에 있는 홀수의 개수가 같은 지점입니다. 만약 조건을 만족하는 인덱스가 존재하지 않는다면 -1을 반환합니다.

예를 들어 배열이 {4, 3, 2, 1, 2, 4}라고 해보겠습니다. 이때 출력 결과는 2입니다. 인덱스 2의 원소는 2이며, 이 원소의 왼쪽에는 홀수가 하나(3), 오른쪽에도 홀수가 하나(1) 있으므로 조건을 충족합니다.

문제 해결 접근 방법

이 문제는 pair를 원소로 갖는 두 개의 벡터를 만들어 해결할 수 있습니다. 하나는 왼쪽 정보를, 다른 하나는 오른쪽 정보를 저장하는 용도입니다. 왼쪽 벡터에는 각 위치를 기준으로 왼쪽에 있는 홀수와 짝수의 개수를 순서대로 기록하고, 오른쪽 벡터에는 오른쪽 구간에 대해 동일한 작업을 수행합니다. 이후 두 벡터를 나란히 비교하여 짝수 개수가 서로 같거나 홀수 개수가 서로 같은 첫 번째 인덱스를 찾아 반환하면 됩니다.

알고리즘

getIndex(arr, n) −

시작
   odd와 even을 선언하고 0으로 초기화
   (홀수, 짝수) 쌍을 담을 left_vector, right_vector 선언
   (odd, even)을 left_vector에 추가
   i를 0부터 n-1까지 반복:
      arr[i]가 짝수이면 even을, 아니면 odd를 1 증가
      (odd, even)을 left_vector에 추가
   반복 끝
   odd := 0, even := 0으로 초기화
   (odd, even)을 right_vector에 추가
   i를 n-1부터 1까지 감소시키며 반복:
      arr[i]가 짝수이면 even을, 아니면 odd를 1 증가
      (odd, even)을 right_vector에 추가
   반복 끝
   right_vector를 뒤집기(reverse)
   left_vector의 각 인덱스 i에 대해:
      left_vector[i].first == right_vector[i].first(홀수 개수 일치)이거나
      left_vector[i].second == right_vector[i].second(짝수 개수 일치)이면 i 반환
   반복 끝
   -1 반환
끝

C++ 구현 예제

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int getIndex(int n, int arr[]) {
    int odd = 0, even = 0;
    vector<pair<int, int>> left_vector, right_vector;
    left_vector.push_back(make_pair(odd, even));
    for (int i = 0; i < n - 1; i++) { // 왼쪽 구간의 홀수·짝수 개수를 계산해 저장
        if (arr[i] % 2 == 0)
            even++;
        else
            odd++;
        left_vector.push_back(make_pair(odd, even));
    }
    odd = 0, even = 0;
    right_vector.push_back(make_pair(odd, even)); // 오른쪽 구간의 홀수·짝수 개수를 계산해 저장
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] % 2 == 0)
            even++;
        else
            odd++;
        right_vector.push_back(make_pair(odd, even));
    }
    reverse(right_vector.begin(), right_vector.end());
    for (int i = 0; i < left_vector.size(); i++) {
        if (left_vector[i].first == right_vector[i].first ||
            left_vector[i].second == right_vector[i].second)
            return i;
    }
    return -1;
}

int main() {
    int arr[] = {4, 3, 2, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = getIndex(n, arr);
    if (index == -1) {
        cout << "-1";
    } else {
        cout << "index : " << index;
    }
}

출력 결과

index : 2

동작 과정 상세 분석

예제 배열 {4, 3, 2, 1, 2}를 기준으로 벡터가 어떻게 채워지는지 살펴보겠습니다.

left_vector: (0,0) → (0,1) → (1,1) → (1,2)
right_vector(뒤집기 전): (0,0) → (0,1) → (1,1) → (1,2) → (2,2)
right_vector(뒤집은 후): (2,2) → (1,2) → (1,1) → (0,1) → (0,0)

두 벡터를 인덱스별로 비교하면 다음과 같습니다.

i = 0 : (0,0) vs (2,2) → 불일치
i = 1 : (0,1) vs (1,2) → 불일치
i = 2 : (1,1) vs (1,1) → 일치, 2 반환

인덱스 2를 기준으로 왼쪽에는 {4, 3}(짝수 1개, 홀수 1개), 오른쪽에는 {1, 2}(짝수 1개, 홀수 1개)가 있어 홀수 개수와 짝수 개수가 모두 일치하므로 2가 반환됩니다.

시간 및 공간 복잡도

배열을 앞에서 한 번, 뒤에서 한 번 순회한 뒤 두 벡터를 한 번 더 비교하므로 시간 복잡도는 O(n)입니다. 왼쪽과 오른쪽 정보를 저장하기 위해 두 개의 보조 벡터를 사용하므로 공간 복잡도 역시 O(n)입니다.