Counting Bits

문제 링크

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

풀이 영상

• https://youtu.be/CNHIHRofKdk?si=ANS9vKrqrMLn-wwQ

분석

n = 5 일때 6개의 배열을 만들고 각 배열에는 2진수 1의 갯수를 입력해야 한다.

[0,1,1,2,1,2] 의 배열이 어떻게 만들어 졌는지 보면

0 -> 0    = 0
1 -> 1    = 1
2 -> 10   = 1
3 -> 11   = 2
4 -> 100  = 1
5 -> 101  = 2

풀이 전략

십진수   이진수    최상위 비트     1의 개수
--------------------------------------------------------
0        0000                        0
1        0001          1             1
2        0010          2             1
3        0011          2             2
--------------------------------------------------------
4        0100          4             1 = 1 + 0 (십진수 0)
5        0101          4             2 = 1 + 1 (십진수 1)
6        0110          4             2 = 1 + 1 (십진수 2)
7        0111          4             3 = 1 + 2 (십진수 3)
--------------------------------------------------------
8        1000          8             1 = 1 + 0 (십진수 0)
9        1001          8             2 = 1 + 1 (십진수 1)
10       1010          8             2 = 1 + 1 (십진수 2)
11       1011          8             3 = 1 + 2 (십진수 3)
--------------------------------------------------------
12       1100          8             2 = 1 + 1 (십진수 4)
13       1101          8             3 = 1 + 2 (십진수 5)
14       1110          8             3 = 1 + 2 (십진수 6)
15       1111          8             4 = 1 + 3 (십진수 7)

• 십진수 - 최상위 비트 = 십진수 -> 이진수 1의 갯수
  1. 십진수 15 빼기 최상위 비트 8을 빼면 7이 나온다.
  2. 십진수 7은 이진수로 변환 시 1의 갯수가 3이다.
  3. 다시 돌아가 십진수 15의 최상위 비트 1 더하기 3을 해서 최종적으로 4가 나온다.
  4. 4는 십진수 15에서 이진수로 변환했을 시 1의 갯수와 동일하다는 것을 알 수 있다.

이것을 공식으로 표현하면

dp[num] = 1 + dp[num - MSB]

• MSB == 최상위 비트

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        msb = 1
        for num in range(1, n + 1):
            if msb << 1 == num:
                msb = num
            dp[num] = 1 + dp[num - msb]
        return dp

공간복잡도와 시간복잡도

이 코드는 n 이하의 모든 수에 대해 1의 비트 개수를 계산하는 함수

시간 복잡도

• dp 배열을 초기화하고, for 루프를 1부터 n까지 돌면서 계산합니다.
• 각 num에 대해 상수 시간 연산(1 + dp[num - msb])만 수행되므로, 루프가 n번 반복됩니다.
• 따라서, 시간 복잡도는 O(n)입니다.

공간 복잡도

• dp 배열은 입력 크기 n에 비례하는 크기를 가지며, n+1 길이의 배열을 사용합니다.
• 변수 msb는 상수 공간을 차지하므로, 추가 공간을 거의 사용하지 않습니다.
• 따라서, 공간 복잡도는 O(n)입니다.

요약

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)