C++의 이진 문자열에서 부분 문자열 010을 제거하는 최소 단계

문제 설명

주어진 이진 문자열에서 작업은 이 이진 문자열에서 부분 문자열 010을 제거하는 최소 단계를 계산하는 것입니다.

예시

입력 문자열이 010010이면 2단계가 필요합니다.

• 처음 0을 1로 변환합니다. 이제 문자열은 110010이 됩니다.
• 마지막 0을 1로 변환합니다. 이제 최종 문자열은 110011이 됩니다.

알고리즘

1. Iterate the string from index 0 sto n-2
2. If in binary string has consecutive three characters ‘0’, ‘1’, ‘0’ then any one character can be changed
Increase the loop counter by 2

예시

#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) { 
   int cnt = 0;
   for (int i = 0; i < str.length() - 2; ++i) {
      if (str[i] == '0' && str[i + 1] == '1' && str[i+ 2] == '0') {
         ++cnt;
         i += 2;
      }
   }
   return cnt;
}
int main() {
   string str = "010010";
   cout << "Minimum required steps = " << getMinSteps(str)
   << endl;
   return 0;
}

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

출력

Minimum required steps = 2