[LeetCode/Easy] 696. Count Binary Substrings

1. Input

1) String s

 

2. Output

1) s의 부분 문자열 중 0과 1의 개수가 같은 부분 문자열의 개수를 반환

- 이때 0은 0끼리, 1은 1끼리 붙어있어야 한다.

 

3. Constraint

1) 1 <= s.length <= 10^5

2) s는 0과 1로 이루어져 있다.

 

4. Example

Input: s = "00110011" -> Output: 6

Input: s = "10101" -> Output: 4

설명:

- “00110011”에서 조건을 만족하는 부분 문자열은 “0011”, “01”, “1100”, “10”, “0011”, “01”의 6개이다. 이때 “00110011”은 0은 0끼리, 1은 1끼리 있지 않기 때문에 조건을 만족하지 못한다.

- “10101”에서 조건을 만족하는 부분 문자열은 "10", "01", "10", "01"의 4개이다.

 

5. Code

1) 첫 코드(2023/05/29)

class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0 ; i<s.length() ; i++){
            int j = i;
            while(j<s.length() && s.charAt(j)==s.charAt(i)) j++;
            list.add(j-i);
            i = j-1;
        }
        for(int i=0 ; i<list.size()-1 ; i++)
            ans += Math.min(list.get(i), list.get(i+1));
        return ans;
    }
}

- 5%, 5%...

 

2) 수정해본 코드(2023/05/29)

class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0, pre = 0;
        for(int i=0 ; i<s.length() ; i++){
            int j = i;
            while(j<s.length() && s.charAt(j)==s.charAt(i)) j++;
            if(pre>0)
                ans += Math.min(pre, j-i);
            pre = j-i;
            i = j-1;
        }
        return ans;
    }
}

- 16%, 7%로 그나마 나아졌다..ㅎ