(Easy - Dynamic Programming) Leetcode - 338. Counting Bits

정수 n이 주어지면 0부터 n까지의 숫자를 2진수로 변환했을 때 각각의 2진수에 1이 몇 개인지세는 문제입니다.

0부터 n까지의 수이므로 정답 배열의 크기는 n + 1이 됩니다.

 

가장 간단한 방법은 매번 10진수를 2진수로 변환할 때 1의 개수를 세는 방법입니다.

10진수를 2진수로 바꾸기 위해서는 2로 나눈 값과 나머지로 2진수를 구해줍니다.

2진수를 구하는게 아닌 2진수로 변환되었을 때 1의 개수를 구하면 되므로 나머지 값을 전부 더해주면 됩니다.

    int CountBitHelper(int n) {
        int bit = 0;
        while (n) {
            bit += n % 2; // 2진수가 필요한게 아닌 2진수의 1의 개수만 세면 된다.
            n /= 2;
        }
        return bit;
    }

  

이 방법을 0부터 n까지의 숫자에 적용해주면 됩니다.

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 0; i <= n; i++) 
        ans[i] = CountBitHelper(i);
		   
    return ans;
}

 

위의 방법은 2진수로 변환하는데 O(n log)의 시간이 필요하고 n까지의 숫자에 적용하니 O(n log n)의 시간이 걸립니다.

 

하지만 Dynamic Programming을 사용하면 O(n)의 시간 안에 해결할 수 있습니다.

10진수에서 2진수로 변환할 때 2로 나누어 갑니다.

즉, 숫자 i의 1의 개수는 숫자 i / 2의 개수에 i % 2를 더하면 1의 개수를 구할 수 있습니다.

i가 만약 홀수라면 i % 2에 의해 1이 더해지고 짝수라면 0이 더해져 i / 2와 1의 개수가 같아집니다.

 

ex) 숫자 5 = 2진수 101

      이때 5 / 2 = 2가 되고 2는 2진수로 10입니다.

      즉, 숫자 5는 2의 2진수 값에 5 % 2 = 1을 맨 뒤에 더해준 것과 같습니다.

      (10진수에서 2진수로 변환할 때 나머지 값을 맨 마지막에 추가해주는 것과 동일)

      10을 밀어줘 100이 되고 1을 추가하면 101이 됩니다.

 

ex) 숫자 7인 경우 = 111,

      7 / 2 = 3이 되고 3의 2진수 값 = 11

     7 % 2 = 1 => 110 + 1 = 111으로 7과 같다. 

    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);

        for (int i = 1; i <= n; i++) 
            // 10진수에서 2진수로 변환할 때 2로 나누는데
            // ans[i / 2]는 i의 이전 bit의 개수와 같다.
            // 그리고 i가 홀수면 i % 2로 인해 1이 추가된다.
            ans[i] = ans[i / 2] + i % 2;
        
        return ans;
    }