C++에서 모든 1을 함께 그룹화하는 데 필요한 최소 스왑

문제 설명

0과 1의 배열이 주어집니다. 작업은 배열에 있는 모든 1을 함께 그룹화하는 데 필요한 최소 스왑 수를 찾는 것입니다.

예시

입력 배열 ={1, 0, 1, 1, 0, 1}이면 1개의 스왑이 필요합니다. 즉, 처음 0을 마지막 1로 바꿉니다.

알고리즘

• 배열의 총 1 수 계산
• count가 x이면 최대 개수가 1인 이 배열의 길이가 x인 하위 배열을 찾아야 합니다.
• 최소 스왑은 길이 x의 하위 배열에서 0의 수이고 최대 수는 1입니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
   int oneCnt = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] == 1) {
         ++oneCnt;
      }
   }
   int x = oneCnt;
   int maxOnes = INT_MIN;
   int preCompute[n] = {0};
   if (arr[0] == 1) {
      preCompute[0] = 1;
   }
   for (int i = 1; i < n; ++i) {
      if (arr[i] == 1) {
         preCompute[i] = preCompute[i - 1] + 1;
      } else {
         preCompute[i] = preCompute[i - 1];
      }
   }
   for (int i = x - 1; i < n; ++i) {
      if (i == (x - 1)) {
         oneCnt = preCompute[i];
      } else {
         oneCnt = preCompute[i] - preCompute[i - x];
      } if (maxOnes < oneCnt) {
         maxOnes = oneCnt;
      }
   }
   int swapCnt = x - oneCnt;
   return swapCnt;
}
int main() {
   int arr[] = {1, 0, 1, 1, 0, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
   return 0;
}

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

출력

Minimum swap count = 1