#002 : Count Binary Substrings

LeetCode Note #002

---

어렵진 않지만, 독특한 방법으로 푸는 문제가 있어 올려봅니다.
LeetCode의 696번 문제 "Count Binary Substrings"입니다.

• https://leetcode.com/problems/count-binary-substrings/description/

[ Description ]

string s가 주어지고, 이 string에서 아래의 조건에 맞는 Substrings의 개수를 출력해야합니다.

1. 비어있지 않음
2. 0과 1의 개수가 동일
3. 0의 모임과 1의 모임이 연속적

   [ NOTE ]

   • 1 ≤ s.length ≤ 50,000
   • s는 0과 1로만 구성

예시로, "00110011"이 입력되면 6을 반환하면 됩니다.
왜 그러한지는 다음과 같습니다.

• s[0]부터 탐색 : 0011 → OK
• s[1]부터 탐색 : 01 → OK
• s[2]부터 탐색 : 1100 → OK
• s[3]부터 탐색 : 10 → OK
• s[4]부터 탐색 : 0011 → OK
• s[5]부터 탐색 : 01 → OK
• s[6]부터 탐색 : 1 → DENY
• s[7]부터 탐색 : 1 → DENY

아래는 Solution에 대한 설명이므로, 지금 보고 싶지않다면 내리지말아주세요.

[ Solution ]

방법 #1 - Group By Character [Accepted]

s의 연속적인 동일 원소들의 개수를 배열에 저장

알고리듬

1. string s에서 연속적으로 동일한 원소가 나타나는 횟수를 뽑습니다.
2. 1에서 뽑은 값을 배열 groups에 저장합니다.
3. 모든 Substrings는 n개의 0, n개의 1 또는 m개의 1, m개의 0의 구조를 가집니다.
4. groups에는 연속적인 0의 개수와 연속적인 1의 개수가 번갈아서 저장되었습니다.
5. min(groups[i-1], groups[i])로 얻는 값은 해당 연속적인 0의 개수와 연속적인 1의 개수로 만들어질 수 있는 Substrings의 개수입니다. ("0011"의 경우 Substrings로 "0011"과 "01"을 추출할 수 있음)
6. groups의 모든 원소에 대해 5의 연산을 행하고, 이 값들을 모두 더하여 return합니다.

   [ 예시 : "00110011" ]

   • groups = { 2, 2, 2, 2 };
   • result = min(groups[0], groups[1]) + min(groups[1], groups[2]) + min(groups[2], groups[3]);
   • return result; → OUTPUT : 6

복잡도 분석

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)

C++ 구현

int countBinarySubstrings(string s)
{
    // groups
    vector<int> groups;
    // 몇 번이나 연속되는지 저장
    // s의 최소 길이는 1이므로, 초기값을 1로 설정
    int countSeq = 1;
    // 정답
    int result = 0;
 
    for (int i = 1; i < s.size(); ++i)
    {
        if (s[i] != s[i - 1])
        {
            groups.push_back(countSeq);
            countSeq = 1;
        }
        else
        {
            ++countSeq;
        }
    }
    // s의 끝부분은 if문으로 걸러낼 수 없기 때문에 따로 삽입
    groups.push_back(countSeq);
 
    for (int i = 1; i < groups.size(); ++i)
    {
        result += min(groups[i - 1], groups[i]);
    }
    return result;
}

---

방법 #2 - Linear Scan [Accepted]

아직 작성 중입니다.

이상입니다.