C++에서 문자열을 모노톤 증가로 뒤집기

<시간/>

'0'과 '1'의 문자열이 주어진다고 가정합니다. 해당 문자열은 '0'(0일 수도 있음)에 이어 '1'(0일 수도 있음)로 구성된 경우 단조롭게 증가합니다. 우리는 '0'과 '1'의 문자열 S를 가지고 있으며 '0'을 '1'로 또는 '1'을 '0'으로 뒤집을 수 있습니다. S 모노톤을 증가시키기 위한 최소 뒤집기 횟수를 찾으십시오. 따라서 입력이 "010110"과 같으면 출력은 2가 됩니다. 뒤집으면 "011111" 또는 "000111"을 얻을 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=S의 크기, 설정 flipCount :=0, oneCount :=0
0 ~ n – 1 범위의 i에 대해
- S[i]가 0이면
  - oneCount =0이면 다음 반복으로 건너뜁니다.
  - flipCount 1 증가
- 그렇지 않으면 oneCount를 1만큼 증가
- oneCount 를 설정합니다.
flipCount 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minFlipsMonoIncr(string S) {
      int n = S.size();
      int flipCount = 0;
      int oneCount = 0;
      for(int i = 0; i < n; i++){
         if(S[i] == '0'){
            if(oneCount == 0) continue;
            flipCount++;
         } else oneCount++;
            if(oneCount < flipCount) flipCount = oneCount;
      }
      return flipCount;
   }
};
main(){
   Solution ob;
   cout << (ob.minFlipsMonoIncr("010110"));
}

입력

"010110"