Counting Bits

1) 문제분석

  num이라는 음이 아닌 정수가 주어졌을 때, 0부터 num까지의 각 정수를 이진수로 표현했을 때 1의 개수를 차례로 벡터에 저장해서 반환하는 메소드를 작성해야 한다. 가장 쉽게 생각할 수 있는 방법은, bit연산을 이용해서 각 정수 i에 대해 0과 1의 개수를 하나씩 살펴볼 수 있는데, 이렇게 하는 경우 시간 복잡도가 O(n*sizeof(int))가 된다. 하지만 시간 복잡도를 O(n)까지 줄일 수 있다고 해서 방법을 고민해보았는데, 이진법 표현이 계속 반복된다는 점을 이용하였다. 예를 들어, 8이상의 수에서는 000, 001, 010, 011, 100, 101, 110, 111이 반복된다.

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> count;
        int k = 1;
        
        
        count.push_back(0);
        for(int i=1; i<=num; i++){
            if(i==k*2)
                k*=2;
            count.push_back(count[i-k]+1);
        }
        
        return count;
    }
};

이렇게 했을 때 답은 맞았지만 코드를 더 최적화해서 시간을 줄일 수 있다. 가령, count[i]의 값은 count[i/2]+i%2 와 같다. i/2의 값은 이진법에서 생각해보면 i»1 연산과 같은데, i가 k개의 bit로 표현된다고 했을 때 상위 k-1 bit의 개수는 count[i/2]와 같고, k번째 bit가 1인지 0인지는 i%2로 판단할 수 있다.