최소 토글은 이진 배열을 분할하여 C++에서 처음 0과 1을 갖도록 합니다.

문제 설명

0과 1만 포함하는 n개의 정수 배열이 주어지면 배열이 분할되는 배열에 필요한 최소 토글(0에서 1로 또는 그 반대로 전환)을 찾으십시오.

예시

arr[] ={1, 0, 0, 1, 1, 1, 0}이면 첫 번째 1과 마지막 0을 전환하는 2개의 토글이 필요합니다.

알고리즘

• 질문을 관찰하면 0에서 n-1까지의 점이 분명히 존재한다는 것을 알게 될 것입니다. 여기에서 해당 지점까지의 모든 요소는 모두 0을 포함해야 하고 오른쪽에서 지점은 모두 1을 포함해야 합니다.
• 이 법을 준수하지 않는 지수는 제거해야 합니다. 아이디어는 왼쪽에서 오른쪽으로 모두 0을 세는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
   int zeroCnt[n + 1] = {0};
   for (int i = 1; i <= n; ++i) {
      if (arr[i - 1] == 0) {
         zeroCnt[i] = zeroCnt[i - 1] + 1;
      } else {
         zeroCnt[i] = zeroCnt[i - 1];
      }
   }
   int result = n;
   for (int i = 1; i <= n; ++i) {
      result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
   }
   return result;
}
int main() {
   int arr[] = {1, 0, 0, 1, 1, 1, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

출력

Minimum toggles = 2