C++에서 양쪽에 짝수 또는 홀수의 개수가 동일한 배열 인덱스

여기서 우리는 하나의 배열이 주어진다고 가정할 때 하나의 문제를 보게 될 것입니다. n개의 요소가 있습니다. 왼쪽의 짝수의 빈도와 오른쪽의 짝수의 빈도가 같거나 왼쪽의 홀수의 빈도와 오른쪽의 홀수의 빈도가 같은 하나의 인덱스를 찾아야 합니다. 그러한 결과가 없으면 -1을 반환합니다.

배열이 {4, 3, 2, 1, 2, 4}와 같다고 가정합니다. 출력은 2입니다. 인덱스 2의 요소는 2이고 왼쪽에 홀수가 하나만 있고 오른쪽에도 홀수가 하나만 있습니다.

이 문제를 해결하기 위해 왼쪽 및 오른쪽 정보를 저장할 두 쌍의 벡터를 생성합니다. 왼쪽에 대한 벡터는 왼쪽의 홀수 및 짝수의 빈도를 저장하고 오른쪽에 대한 벡터는 오른쪽에 대해 동일한 작업을 수행합니다. 왼쪽과 오른쪽의 짝수 개수 또는 왼쪽과 오른쪽의 홀수 개수가 같으면 인덱스를 반환합니다.

알고리즘

getIndex(arr, n) -

Begin
   define odd and even, and initialize as 0
   define left_vector, right_vector for odd even pairs
   add (odd, even) into left_vector
   for i in range 0 to n-1, do
      if arr[i] is even, then increase even, otherwise increase odd
         add (odd, even) into left_vector
   done
   odd := 0 and even := 0
   add (odd, even) into right_vector
   for i in range n-1 down to 1, do
      if arr[i] is even, then increase even, otherwise increase odd
         add (odd, even) into right_vector
   done
   reverse the right_vector
   for each element at index i in left_vector, do
      if left_vector[i].first = right_vector[i].first, or left_vector[i].odd= right_vector[i].odd, then return i
   done
   return -1
End

예시

#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++) { //count and store odd and even frequency for left side
      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)); //count and store odd and even frequency for right side
   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