Blind 75 | Counting Bits (Bit Manipulation 2 / 5)

https://leetcode.com/problems/counting-bits/

Counting Bits - LeetCode

 

Counting Bits - 비트 세기

 

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

정수 n이 주어졌을때 0부터 n까지 1 비트의 갯수가 담긴 배열을 리턴하라.

 

 

 

풀이

 

1) 빌트인 메서드를 사용한 무식한 방법 (내 풀이)

 

0부터 n까지 

i.toString(2).split('').filter((c) => c === '1').length;

 

를 돌린다.. 무식하고 비효율적인 방법이다.

 

 

2) DP를 이용해서 전에 계산한 값을 이용하는 방법

 

0 - 0000 = 0

1 - 0001 = 1 => 1 + dp[n - 1]

2 - 0010 = 1 => 1 + dp[n - 2]

3 - 0011 = 2 => 1+ dp[n - 2]

4 - 0100 = 1 => 1 + dp[n - 4]

5 - 0101 = 2 => 1 + dp[n - 4]

6 - 0110 = 2 => 1 + dp[n - 4]

7 - 0111 = 3 => 1 + dp[n - 4]

8 - 1000 = 1 =>1 + dp[n - 8]

법칙을 발견하고 풀어라..

이건데 종이에 그려보면서 법칙을 발견하고 dp를 이용해서 풀어라... 그런 문제 같다.. 어렵다..

 

 

코드

 

 

코드로 표현하면 이렇다.