[LeetCode] 338. Counting Bits

338. Counting Bits

LeetCode

 

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 <= i <= n 인 각 i에 대하여 ans[i]가 i를 이진수로 나타냈을 때의 1의 개수가 되는, 길이가 n + 1인 배열 ans를 반환하세요.

 

Example

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

---

1. 문제 요구사항 분석

0 ~ n 까지 이진수로 표현한 후, 1의 개수 구하기

 

2. 접근 전략

파이썬은 bin이라고 제공되고 있는 함수가 있기 때문에 파이썬으로 1차 구현 후, 자바로 변환해보는 작업을 진행해봄

 

[파이썬]

class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """

        return [bin(i).count("1") for i in range(n + 1)]

 

[자바]

자바에도 Integer.bitCount 라는 함수 제공

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            result[i] = Integer.bitCount(i);
        }

        return result;
    }
}

 

DP로 풀어보기

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1); // ans[i] = ans[i / 2] + (i % 2);
        }

        return ans;
    }
}

ans[0] = 0
ans[1] = ans[0] + 1
ans[2] = ans[1] + 0
ans[3] = ans[1] + 1
ans[4] = ans[2] + 0
ans[5] = ans[2] + 1

...

 

숫자 i의 이진수는, i/2의 이진수 뒤에 마지막 비트 하나를 붙인 것과 같다 !!!!!