Counting Bits

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

Counting Bits - LeetCode

 

bit의 개수를 새는 문제로 특정 숫자가 아니라 n까지의 모든 개수를 세는 문제이다. n이 충분히 크다면 속도가 굉장히 느려질 것을 예상해서 문제를 풀어야 할 것으로 추측할 수 있다. dp 방식으로 기존의 값에서 개수를 가져와야 빠르게 샐 수 있다. 이진수는 커질수록 자리수가 늘어난다는 점에서 착안하면 점화식을 세울 수 있다.

2, 3과 4의 이진수는 아래와 같다. 

 

2 - 10
3 - 101
4 - 100

 

3과 4는 2의 이진수에 1과 0이 추가된 형태이다. 2가 가진 1의 개수를 알 수 있다면 3의 경우 1개 추가된 것이고, 4의 경우 0개 추가되어 같은 것이다. 위와 같이 2와 3,4의 관계는 비트 이동 연산자를 통해 쉽게 찾을 수 있다. 3과 4의 비트를 오른쪽으로 한 칸 이동하면 되기 때문이다. 이와 같은 생각을 바탕으로 점화식을 세워 아래와 같이 풀 수 있다.

public class Solution {  
    public int[] countBits(int n) {  
        int[] ans = new int[n + 1];  
        for(int i = 0; i <=n; i++){  
            int cnt = 0;  
            ans[i] = ans[i >> 1] + (i & 1);  
        }  
  
        return ans;  
    }  
}