Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 이진 부분 문자열 개수 구하는 방법

문제 이해하기

문자열 s가 주어졌을 때, 다음 두 조건을 모두 만족하는 연속된(contiguous) 부분 문자열의 개수를 구해야 합니다.

  • 부분 문자열 안에 포함된 0과 1의 개수가 서로 같아야 합니다.
  • 모든 0은 한 덩어리로, 모든 1도 한 덩어리로 연속되게 배치되어 있어야 합니다.

동일한 부분 문자열이 여러 번 등장하면, 등장할 때마다 각각 따로 세어 줍니다.

예를 들어 입력이 "11001100"이라면 정답은 6입니다. 조건을 만족하는 부분 문자열은 "1100", "10", "0011", "01", "1100", "10" 입니다.

접근 방법

이 문제는 문자열을 한 번만 순회하면 되는 O(n) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 "현재 숫자가 연속으로 이어진 길이"와 "바로 앞 숫자가 연속으로 이어졌던 길이"를 함께 추적하는 것입니다. 현재 그룹의 길이가 직전 그룹의 길이보다 작거나 같아지는 순간마다, 두 그룹의 경계에 걸친 유효한 부분 문자열이 하나씩 새로 만들어집니다.

알고리즘 단계

  1. 크기가 2인 배열 cnt를 선언하고 0으로 초기화합니다.
  2. 결과를 저장할 변수 res를 0으로 초기화합니다.
  3. i를 0부터 문자열 길이 - 1까지 1씩 증가시키며 다음을 반복합니다.
    • num := s[i] - '0' 으로 현재 문자를 숫자(0 또는 1)로 변환합니다.
    • i가 0이거나 s[i]가 s[i-1]과 다르면, 즉 숫자 그룹이 바뀌었다면 cnt[num] := 0으로 초기화합니다.
    • cnt[num]을 1 증가시킵니다.
    • cnt[num] <= cnt[1 - num]이면 res를 1 증가시킵니다.
  4. 반복이 끝나면 res를 반환합니다.

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#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"

출력

6