haklee.py

"""TC: O(n), SC: O(n)

아이디어:
- bin으로 변환한 값의 길이가 k인 모든 수들에 대한 bit_count값을 알고 있다고 하자.
- 사실 위의 수들은 bin으로 변환했을때 맨 앞 자리가 0으로 시작하는 길이 k+1의 수라고 볼 수 있다.
- 그렇다면 bin으로 변환했을때 맨 앞 자리가 1로 시작하는 길이 k+1인 수들의 bit_count는
    맨 앞 자리가 0으로 시작하는 수들의 bit_count에 1을 더한 것이라고 할 수 있다.
- 위의 아이디어를 활용하면 앞 2^k 수들의 bit_count를 알고 있으면 간단한 더하기 연산을 통해
    이후 2^k 수들의 bit_count값도 알 수 있다.
    e.g.)
    - 0, 1의 bit_count가 [0, 1]이라면, 2, 3의 bit_count는 [0+1, 1+1], 즉, 0~3의 bit_count는 [0, 1, 1, 2]
    - 0~3의 bit_count가 [0, 1, 1, 2]라면, 4~7의 bit_count는 [1, 2, 2, 3], 즉, 0~7의 bit_count는
        [0, 1, 1, 2, 1, 2, 2, 3]
    - ...
- 리스트의 크기를 2배씩 늘리다가 n보다 커졌을때 앞 n개의 아이템만 취해서 리턴.


SC:
- 아래에서 리스트 s의 길이는 2^(k-1) < n <= 2^k를 만족하는 2^k만큼 커진다.
- 즉, O(n).

TC:
- s 안에 들어있는 i번째 아이템을 계산할때 필요한 연산은 덧셈 1회, 즉, O(1).
- i번째 아이템 값을 구하기 위해 그 앞의 값을 미리 계산해둔 것이라 생각할 수 있다.
- SC 분석과 비슷하게, 2^(k-1) < n <= 2^k를 만족하는 2^k만큼 반복. 즉, O(n).
"""


class Solution:
    def countBits(self, n: int) -> List[int]:
        s = [0]
        m = n * 2
        while m := m >> 1:
            s += [i + 1 for i in s]
        return s[: n + 1]