[LeetCode/Easy] 338. Counting Bits

1. Input

1) 정수 n

 

2. Output

1) 0부터 n까지의 정수를 2진수로 표현한 문자열에서 나타나는 1의 개수를 담은 int 배열

 

3. Constraint

1) 0 <= n <= 10^5

 

4. Example

Input: n=5 -> Output: {0,1,1,2,1,2}

설명: 0부터 5까지의 정수를 숫자 -> 2진수 -> 1의 개수로 표현해보면

0 -> 0 -> 0

1 -> 1 -> 1

2 -> 10 -> 1

3 -> 11 -> 2

4 -> 100 -> 1

5 -> 101 -> 2

 

5. Code

1) 첫 코드(2022/06/16)

if(n == 0) return new int[] {0};

int[] ans = new int[n+1];
ans[0] = 0;

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

2) 배운걸 토대로 수정해본 코드(2022/11/29)

int[] answer = new int[n+1];
for(int i=0 ; i<=n ; i++)
    answer[i] = Integer.bitCount(i);
return answer;

  - 압도적으로 빠르다.