C++에서 왼쪽이 모두 1이고 오른쪽이 0이 되도록 최소 뒤집기

문제 설명

왼쪽 부분의 모든 1과 오른쪽 부분의 모든 0을 뒤집을 수 있는 이진 문자열이 주어집니다. 작업은 왼쪽에 모두 1을, 오른쪽에 모두 0을 만드는 데 필요한 최소 뒤집기를 계산하는 것입니다.

예시

주어진 이진 문자열은 0010101입니다. 이 문자열에는 3개의 1비트와 4개의 0비트가 있습니다. 아래 표시된 것처럼 강조 표시된 4비트를 뒤집어 왼쪽에 모두 1을 만들고 오른쪽에 모두 0을 만들어야 합니다. -

0010101

문자열을 뒤집은 후에는 -

1110000

알고리즘

• 문자열을 왼쪽에서 오른쪽으로 탐색하고 모든 0을 1로 변환하는 데 필요한 뒤집기 횟수를 계산합니다.
• 문자열을 오른쪽에서 왼쪽으로 탐색하고 모든 1을 0으로 바꾸는 데 필요한 뒤집기 횟수를 계산합니다.
• 비트 사이의 모든 위치를 탐색하고 (0의 뒤집기 + 1의 뒤집기) 최소값을 찾습니다.

예시

#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
   int n = binaryString.length();
   int flipCnt, zeroFlips[n], oneFlips[n];
   flipCnt = 0;
   for (int i = 0; i < n; ++i) {
      if (binaryString[i] == '0') {
         ++flipCnt;
      }
      zeroFlips[i] = flipCnt;
   }
   flipCnt = 0;
   for (int i = n - 1; i >= 0; --i) {
      if (binaryString[i] == '1') {
         ++flipCnt;
      }
      oneFlips[i] = flipCnt;
   }
   int minFlips = INT_MAX;
   for (int i = 1; i < n; ++i) {
      int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
         minFlips = sum;
      }
   }
   return minFlips;
}
int main() {
   string binaryString = "0010101";
   cout << "Minimum flips: " << minFlips(binaryString) <<
   endl;
   return 0;
}

출력

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

Minimum flips: 4