.Zzumbong

[leetCode/JS] 696. Count Binary Substrings 본문

coding test/leetCode

[leetCode/JS] 696. Count Binary Substrings

쭘봉 2022. 11. 23. 11:34

문제 설명

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.

 

입출력 예

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.

 

Constraints

  • 1 <= s.length <= 105
  • s[i] is either '0' or '1'.

내 솔루션

  • 뭔지 모르겠지만.. 손코딩하면서 알아낸 규칙으로 풀었다.
  • 다 풀고나서 for문을 1번으로 줄이고 싶었으나 시간이 없어 포기
  • prev를 문자를 비교 하지말고 prevCount로 받아서 현재 count와 이전 카운트를 비교하여 작은 수를 바로 저장하여 리턴하면 될 뜻.
var countBinarySubstrings = function(s) {
  const map = [];
  let res = 0;
  let prev = null;
  let tempCount = 0;
  for(let i = 0 ; i < s.length ; i++){
    if(prev === s[i]) {
      tempCount++;
    } else {
      prev = s[i];
      if(i !== 0) map.push(tempCount)
      tempCount = 1;
    }
  }
  map.push(tempCount)
  for(let i = 0; i < map.length - 1; i++) {
    res += Math.min(Number(map[i]), Number(map[i + 1]))
  }
  return res;
};

최고의 솔루션

  • 뭐하는 녀석이지. 대단하다..
const countBinarySubstrings = (s) => s.replace(/01/g, '0,1').replace(/10/g, '1,0').split(',')
    .reduce((res, a, i, arr) => i ? res + Math.min(a.length, arr[--i].length) : 0, 0);
// input 00110011
// ['00', '11', '00', '11']
// i가 0이 아닐 때부터, '00' , '11' 비교하여 작은 length를 res에 더함.
// res를 리턴함.

감상평

  • 분명 easy 난이도 였는데, 풀고나선 더 어렵게 느껴진다.
  • replace로 array로 나눌줄은 상상도 못했다.
Comments