[Leetcode] 696. Count Binary Substrings

696. 이진 문자열 계산하기

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.

이진문자열이 주어지면 똑같은 개수의 0과 1로 이루어진 비어있지 않은 부분문자열을 리턴해여라.
그리고 0과 1의 부분문자열들은 연속하여 그룹지어져있다.
여러번 반복되는 부분문자열은 그들이 발생되는 횟수만큼 계산됩니다.

 

Example 1:

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

 

Example 2:

Input: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

 

이 문제의 key point는 0과 1이 같은 개수로 포함된 부분문자열만 count 한다는 점이다.

따라서 "00011" 은 0이 한개 더 많이 들어있기 때문에 부분문자열로 인정받지 못한다.

 

0과 1의 연속되는 숫자를 각각 담기 위하여 Two Pointers 방식을 이용하였다.

 

나의 풀이

import java.util.LinkedList;
import java.util.Queue;
import java.lang.Math;

class Solution {
    // 0의 연속된 개수를 세는 포인터
    Queue<Integer> zeroQueue = new LinkedList<>();
    // 1의 연속된 개수를 세는 포인터
    Queue<Integer> oneQueue = new LinkedList<>();
    
    public int result = 0;
    public int sLength = 0;
    String fullS = "";
    String curStr = "";
    
    // s의 처음부터 끝까지 모든 문자열을 추출한다.
    public int countBinarySubstrings(String s) {
        sLength = s.length();
        fullS = s;
        for(int i=0; i<s.length(); i++){
            curStr = s.substring(i, i+1);
            switch(curStr){
                case "0":
                    keepZero(i);
                    break;
                case "1":
                    keepOne(i);
                    break;
            }
        }
        return result;
    }
    
    public void keepZero(int index){
        zeroQueue.add(0);
        // 마지막 문자열 처리
        if(sLength - 1 == index){
            result += getMinQueueSize();
            return;
        }
        
        if(oneQueue.size() > 0 && fullS.substring(index+1, index+2).equals("1")){
            result += getMinQueueSize();
            oneQueue.clear();
        }
    }
    
    public void keepOne(int index){ // 001111110011
        oneQueue.add(1);
        // 마지막 문자열 처리
        if(sLength - 1 == index){
            result += getMinQueueSize();
            return;
        }
        if(zeroQueue.size() > 0 && fullS.substring(index+1, index+2).equals("0")){
            result += getMinQueueSize();
            zeroQueue.clear();
        }
    }
    
    public int getMinQueueSize(){
        return Math.min(zeroQueue.size(), oneQueue.size());
    }
}

 

좋은 풀이 참고

class Solution {
    public int countBinarySubstrings(String s) {
        int all = 0;
        int nowCount = 0;
        int prevCount = 0;
        char prev = ' ';
        
        for (char c: s.toCharArray()) {
            if (prev == c) {
                nowCount++;
            } else {
                prev = c;

                all += Math.min(prevCount, nowCount);
                prevCount = nowCount;
                nowCount = 1;
            }
        }
        
        all += Math.min(prevCount, nowCount);
        return all;
    }
}

 

스트링 문자열을 아예 처음부터 char배열로 변한한뒤 매번 char 자료형으로 비교한다.

이렇게 비교하면 매번 heap영역에 메모리를 할당하지 않아도 되므로 공간복잡도와 시간복잡도가 줄어들 것으로 예상된다.

 

전체적으로 보면 0 혹은 1의 연속적으로 발생한 숫자를 prevCount에 담아 놓고 현재 다른 문자인 0혹은 1을 세는 nowCount에 담아서 더 작은 값 Math.min 값을 반환하여 부분문자열의 개수에 더한다는 점이 내 코드와 흡사하지만 많은 부분을 간결하게 줄였다.