[LeetCode] 338. Counting Bits - Java

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

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 0 <= n <= 105

---

풀이

풀이 과정

0부터 n까지 비트로 표현하였을 때 각 수마다 1인 비트의 개수를 구하는 문제이다.

우선 오른쪽 shift 연산의 특징을 파악해본다.
비트의 각 자리는 오른쪽 부터 1, 2, 4, 8...과 같이 1부터 두 배씩 증가한다. 그렇기 때문에 오른쪽으로 한 자리씩 옮긴다는 것은 각 자리마다 두 배씩 작아지는 것을 의미한다. 즉 오른쪽으로 1만큼 shift 하는 것은 n을 2로 나눈 것과 같다.

그렇다면 n에서 비트의 개수는 n을 2로 나눈 몫의 비트의 개수에서 오른쪽으로 밀려 사라진 마지막 비트의 합이라고 볼 수 있다. 이 때 마지막 비트가 1인지 아닌지는 n과 1을 AND 연산하여 구할 수 있다.

따라서 n에 대해 다음과 같이 정리할 수 있다.

n이 0일 때 -> 1비트의 개수 == 0
n이 1일 때 -> 1비트의 개수 == (1 / 2)의 1비트 개수 + (1 & 1) == 0의 1비트 개수 + 1
n이 2일 때 -> 1비트의 개수 == (2 / 2)의 1비트 개수 + (2 & 1) == 1의 1비트 개수 + 0
n이 3일 때 -> 1비트의 개수 == (3 / 2)의 1비트 개수 + (3 & 1) == 1의 1비트 개수 + 1
...
n일 때 -> 1비트의 개수 == (n / 2)의 1비트 개수 + (n & 1)

0부터 n까지 반복하며 각 인덱스에 값을 저장하며 동적프로그래밍을 이용하여 O(n)의 시간복잡도로 문제를 해결이 가능하다.

---

최종 코드

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

        /*
         * 오른쪽 shift( >> ) 는 2로 나눈 값과 같음
         * 따라서 n에서 1 비트의 개수는 n의 마지막 비트와
         * n을 2로 나눈 수( 오른쪽으로 shift한 값 )의 비트의 합과 같음
         */
        for(int i = 1; i <= n; i++){
            answer[i] = (i & 1) + answer[i/2];
        }

        return answer;
    }
}

---