C++에서 이진 부분 문자열 계산

<시간/>

문자열 s가 있다고 가정하고 0과 1의 수가 같은 연속적인 하위 문자열의 수를 찾아야 하며 이러한 하위 문자열의 모든 0과 모든 1이 연속적으로 그룹화됩니다. 부분 문자열이 여러 번 발생하면 발생한 횟수로 계산됩니다.

따라서 입력이 "11001100"과 같으면 하위 문자열이 "1100", "10","0011", "01", "1100", "10"이므로 출력은 6이 됩니다.

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

크기가 2인 배열 cnt를 정의하고 0으로 채웁니다.
res :=0
초기화 i의 경우:=0, i <길이 s일 때 업데이트(i를 1만큼 증가), 수행 -
- num :=s[i] - '0'의 ASCII
- i가 0과 같거나 s[i]가 s[i - 1]과 같지 않으면 -
  - cnt[숫자] :=0
- (cnt[num]을 1씩 증가)
- cnt[num] <=cnt[1 - num]이면 -
  - (해상도 1 증가)
반환 결과

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int countBinarySubstrings(string s) {
      int cnt[2] = { 0 };
      int res = 0;
      for (int i = 0; i < s.length(); ++i) {
         int num = s[i] - '0';
         if (i == 0 || s[i] != s[i - 1])
            cnt[num] = 0;
         ++cnt[num];
         if (cnt[num] <= cnt[1 - num])
            ++res;
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.countBinarySubstrings("11001100"));
}

입력

"11001100"