Leetcode 338. Counting Bits

문제

Given an integer n, 
return an array ans of length n + 1 such that for each i (0 <= i <= n), 
ans[i] is the number of 1's in the binary representation of i.

정수 n이 주어진다, n+1 크기의 배열을 만들어 배열 값으로 해당 index i를 2진수로 표현했을때 1의 갯수를 가지도록 하십시오.

예시

Input: n = 2
Output: [0,1,1]
Explanation:
index 0 은 0 -> 1이 0개,
index 1 는 1 -> 1이 1개,
index 2 는 10 -> 1이 1개.

제한

• $0 <= n <= 10^5$

풀이법

1. 각자 값을 바로 구한다.

• n개의 숫자에 대해 각각 1의 갯수를 구한다.
• n개의 숫자에 대해 logN의 시간복잡도로 1의 갯수를 구하기에 NlogN 의 시간복잡도를 가진다.

2. Dynamic Programming 을 이용한다.

• 이를 이해하기 위해선 숫자를 일단 나열해볼 필요가 있다.

10진수	2진수
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111

• 여기서 눈여겨 볼 점은 자릿수가 바뀔때이다.
• 2 ~ 3 에서 맨 왼쪽의 자리를 제외한 나머지 2진수 자리는 정확히 0~1의 2진수 표현과 동일하다.
• 4 ~ 7 에서 맨 왼쪽의 자리를 제외한 나머지 2진수 자리는 정확히 0~3의 2진수 표현과 동일하다.
• 즉 미리 구해둔 1의 갯수 + 1만 해주면 된다는 뜻이다!
• 자신이 속한 자릿수의 위치만 구해두면 찾을수 있게 된다

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0 for _ in range(n+1)]

        exp = 1
        # 0은 무조건 포함하기에 1부터 시작한다.
	
    	# 자릿수 값은 n보다는 적어도 같거나 작아야 한다.
        while exp <= n:
        # 해당 자릿수에 해당하는 값을 구하는것
            for i in range(exp, exp * 2):
				# n을 넘어서면 종료한다.
                if i > n: break
                # 값 구하기
                ans[i] = 1 + ans[i - exp]
            # 자릿수 증가
            exp *= 2

        return ans

• 이전에 구했던 값으로 선형적으로 바로 구해지기에 logN의 시간복잡도를 가진다.