(C++) - LeetCode (easy) 696. Count Binary Substrings

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

Count Binary Substrings - LeetCode

구현 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

연속적인 문자열의 길이를 저장할 vector consecutiveList와 cnt를 선언해줍니다.

📔 풀이과정

1. 연속적인 문자열중 0과 1이 같은 것들은 10, 01, 1100, 0011, 111000, 000111... 처럼 1대1로 "0"과 "1"이 1개씩 증가하며 2개씩 증가됩니다.

2. 따라서 연속적인 문자열 들의 길이를 s에 대해 순회하며 consecutiveList vector에 저장해줍니다. 인접한 원소는 값이 항상 다르게 저장되게 됩니다.

3. consecutiveList를 순회하면서 인접값 중 더 작은 값을 ans에 더해줍니다. 11100 인경우 [3, 2] 형식으로 저장되게 되는데 1개수와 0의 개수는 같아야 부분 문자열을 만들 수 있기 때문에 3과 2중 더 작은 값인 2를 ans에 저장해야 합니다.

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    int countBinarySubstrings(string s) {
        vector<int> consecutiveList;
        int cnt = 1;
        for(int i = 1; i < s.size(); i++) {
            if(s[i] == s[i-1]) {
                cnt++;
            } else {
                consecutiveList.push_back(cnt);
                cnt = 1;
            }
        }
        consecutiveList.push_back(cnt);

        int ans = 0;
        for(int i = 1; i < consecutiveList.size(); i++) {
            ans += min (consecutiveList[i-1], consecutiveList[i]);
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.