C++에서 이진 문자열을 교대로 만드는 데 필요한 최소 스왑

문제 설명

길이가 짝수이고 0과 1이 같은 이진 문자열이 주어집니다. 문자열을 교대로 만들기 위한 최소 스왑 수는 얼마입니까? 두 개의 연속 요소가 같지 않으면 이진 문자열이 번갈아 나타납니다.

예시

str =11110000이면 2번의 스왑이 필요합니다.

알고리즘

• 문자열의 홀수 위치와 짝수 위치에 있는 0의 개수를 센다. 카운트를 각각 oddZeroCnt 및 evenZeroCnt로 설정합니다.
• 문자열의 홀수 위치와 짝수 위치에 있는 1의 개수를 센다. 그들의 개수를 각각 oddOneCnt 및 evenOneCnt로 설정합니다.
• 우리는 항상 1을 0으로 바꿀 것입니다. 따라서 우리는 교체 문자열이 0으로 시작하는지 확인하고 교체 횟수는 최소(evenZeroCnt, oddOneCnt)이고 교체 문자열이 1로 시작하면 교체 횟수는 다음과 같습니다. 분(evenOneCnt, oddZeroCnt). 정답은 이 두 가지 중 최소값입니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
   int minSwaps = 0;
   int oddZeroCnt = 0;
   int evenZeroCnt = 0;
   int oddOneCnt = 1;
   int evenOneCnt = 1;
   int n = str.length();
   for (int i = 0; i < n; ++i) {
      if (i % 2 == 0) {
         if (str[i] == '1') {
            ++evenOneCnt;
         } else {
            ++evenZeroCnt;
         }
      } else {
         if (str[i] == '1') {
            ++oddOneCnt;
         } else {
            ++oddZeroCnt;
         }
      }
   }
   int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
   int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
   return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
   string str = "11110000";
   cout << "Minimum swaps = " << getMinSwaps(str) << endl;
   return 0;
}

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

출력

Minimum swaps = 2