Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

이진 문자열을 대체하기 위한 뒤집기 횟수 - C++에서 1로 설정

<시간/>

바이너리 문자열 "10011"을 제공했다고 가정해 보겠습니다. 대체 바이너리 문자열을 만들려면 최소 2자를 "10101"로 뒤집어야 합니다.

대체 문자열에는 두 가지 가능성이 있습니다. 0 또는 1로 시작합니다. 우리는 두 개의 대안을 확인하고 둘 모두에 필요한 뒤집기 횟수를 계산합니다.

그런 다음 둘 중 최소값을 반환합니다. 예를 들어 보겠습니다.

입력 

binary = "10011"

출력 

2

문자열을 0으로 시작하면 3번 뒤집어야 합니다. 그리고 문자열을 1로 시작하면 2번 뒤집어야 합니다. 최소값은 2입니다.

알고리즘

  • 이진 문자열을 초기화합니다.
  • 1부터 시작하는 문자열을 번갈아 가며 만드는 데 필요한 뒤집기 횟수를 센다.
  • 0으로 시작하는 문자열을 번갈아 가며 만드는 데 필요한 뒤집기 횟수도 비슷하게 계산합니다.
  • 위의 두 가지 중에서 최소값을 찾으십시오.
  • 최소한을 인쇄합니다.

구현

다음은 위의 알고리즘을 C++로 구현한 것입니다.

#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
   return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
   int flipCount = 0;
   for (int i = 0; i < binary.length(); i++) {
      if (binary[i] != expected) {
         flipCount++;
      }
      expected = flip(expected);
   }
   return flipCount;
}
int main() {
   string binary = "10011";
   cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary,       '1')) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

2