[리트코드] 338. Counting Bits

in 코딩테스트 on 리트코드




338. Counting Bits

리트코드

나의 풀이 (이진수를 바꾼 문자열을 배열로 만들어 갯수 세기)

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const ans = []
  for(let i = 0; i<=n; i++){
    ans.push([...i.toString(2)].filter(v => v == 1).length)
  }
  return ans
};

console.log(countBits(5));



정규식으로 바꾸기

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const ans = []
  for(let i = 0; i<=n; i++){
    ans.push(i.toString(2).replace(/0/g,'').length)
  }
  return ans
};

정규식으로 바꾸는게 배열로 만들어서 filter를 돌일일도 없으니 훨씬 효율적인 것 같다.
하지만 문제의 주제는 dp!
dp 방법으로 접근해보자



dp로 풀기

/**
 * @param {number} n
 * @return {number[]}
 */
 var countBits = function(n) {
  const result = [0];
  for (let i = 1, prevPow = 1; i <= n; i++) {
      if (((i - 1) & i) === 0) {
          result[i] = 1;
          prevPow = i;
      }
      result[i] = result[i - prevPow] + 1;
      
  }
  return result;
};



번외 : 2진수로 바꿔 1의 갯수 찾기 알고리즘

비트연산자 기본 개념 활용하기 (O(n))

 var countBits = function(n) {
  let cnt = 0
  while(n){
    cnt += n & 1 //마지막 비트가 1이라면 cnt 증가
    n >>= 1 // 마지막 비트 삭제(시프트 연산)
  }
  return cnt
};

console.log(countBits(5));

Brian Kernighan’s Algorithm (O(nlogn))

var countBits = function (n) {
  let cnt = 0;
  while (n) {
    n &= n - 1;
    cnt++;
  }
  return cnt;
};

console.log(countBits(5));