[Leetcode][696] Count Binary Substrings

문제 : https://leetcode.com/problems/count-binary-substrings/

---

0과 1로 이루어진 문자열에서 연속적으로 같은 숫자의 문자가 나오는 부분문자열들의 수를 구하라.

부분문자열 예 : 0011, 01, 10 / 안되는 예 : 1010 (같은 숫자가 연속적이지 않음). 11100 (숫자들의 등장횟수가 다름)

동일한 부분 문자열이라도 여러번 발생하면 발생한 횟수만큼 정답에 더해준다.

---

문자열을 탐색하면서 연속적으로 나오는 0과 1의 수를 센다.

예를 들어, "00110011"이라면

 

인덱스 / 숫자	0	1
0 (0)	1	0
1 (0)	2	0
2 (1)	2	1
3 (1)	2	2
4 (0)	1	2
5 (0)	2	2
6 (1)	2	1
7 (1)	2	2

 

위와 같이 채워진다. 인덱스가 4일 때 연속적으로 나오는 0의 횟수는 1로 초기화 된다. 마찬가지로 인덱스가 6일 때, 1의 횟수는 1로 초기화된다.

이를 보면 탐색하는 문자가 이전과 다른 경우 횟수가 초기화되는 것을 볼 수 있다.

 

만약 문자열 001 중 마지막 문자를 포함하면서 정답이 될 수 있는 부분문자열은 01 이다.

문자열 00111 중 마지막 문자를 포함하면서 정답이 될 수 있는 부분문자열은 존재하지 않는다.

즉, 현재 탐색중인 문자의 연속 등장횟수가 다른 문자의 연속 등장횟수보다 작거나 같다면 정답에 속하는 부분문자열을 만들 수 있고, 그렇지 않다면 부분문자열을 만들 수 없다.

 

위 조건들로 문자열 S를 모두 탐색하면서 정답 수를 갱신해나간다.

 

시간복잡도는 O(N). N = |s|

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/696.%20Count%20Binary%20Substrings.cpp