[Bit Manipulation][Easy] 338. Counting Bits

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. n이 주어질때 0 ~ n 까지의 수를 2진수로 변환하고, 그 2진수에서 1의 개수를 vector로 출력하라. 

 

Solution. 

 bit check의 기본에 해당하는 문제. 

 우선 직관에 근거해 로직은 전개해 풀어 본다.

vector<int> countBits(int n)
{
    vector<int> vRet;
    for (int k = 0; k <= n; ++k)
    {
        int value = k;
        int count = 0;
        while (value)
        {
            if (value & 1)	++count;
            value = value >> 1;
        }
        vRet.push_back(count);
    }
    return vRet;
}

 

 

Outcome.

 

while내의 로직이 단순하여 시간 자체는 나쁘지 않지만,

알고리즘 TC는 NxN 으로 별로 좋아 보이지 않는다. 

그리고 memory usage도 하위 6%로 별로 좋지 않다. 

 

TC를 N으로 최적화 하는 방법을 찾아 보자. 

 

이를 dp 적으로 생각해 보면, 

N의 자리수가 증가함에 따라

X 

1X 

1XX 

1XXX 

1XXXX 

 

즉, N의 1의 개수 f(N)은, f(N/2)의 결과에 1 혹은 2가 더해져서 나온 결과임을 알 수 있다. 

즉, f(N) = f(N/2) + N%2 로 정리가 된다. 

 

vector<int> countBits(int n)
{
    vector<int> vRet;
    vRet.resize(n + 1, 0);
    for (int q = 1; q <= n; ++q)
        vRet[q] = vRet[q / 2] + q%2;

    return vRet;
}

 

 

TC와 memory usage 모두 다소 개선되었다.