Bit: 338. Counting Bits ★★★

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.

 

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

 

Constraints:

• 0 <= n <= 105

 

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

문제 해설

이 문제는 0부터 nnn까지의 정수를 2진수로 변환했을 때, 각 숫자의 1의 개수를 계산하여 배열로 반환하는 문제입니다.

---

문제 조건

1. 입력: 정수 nnn (0≤n≤1050 \leq n \leq 10^50≤n≤105).
2. 출력: 길이가 n+1n + 1n+1인 배열 ansansans로, ans[i]ans[i]ans[i]는 정수 iii의 이진 표현에서 1의 개수를 나타냅니다.

제한 조건

1. O(nlog⁡n)의 복잡도로는 간단하게 해결 가능하지만, 이 문제는 O(n) 시간 복잡도로 해결해야 합니다.
2. 내장 함수 (예: __builtin_popcount)를 사용하지 않고 구현해야 합니다.

 

https://youtu.be/CNHIHRofKdk?si=OnEJ32ZRkdzzE47g

 

 

Code

class Solution:
    def countBits(self, n: int) -> List[int]:
        # DP 배열 초기화: dp[i]는 i의 이진 표현에서 1의 개수를 저장
        dp = [0] * (n + 1)
        # offset: 현재 참조 중인 가장 큰 2의 거듭제곱
        offset = 1

        # 1부터 n까지 순회하면서 dp 배열 계산
        for i in range(1, n + 1):
            # i가 새로운 2의 거듭제곱일 때, offset 업데이트
            if offset * 2 == i:
                offset = i

            # dp[i]는 i의 1의 개수 = dp[i - offset] + 1
            # offset은 가장 가까운 2의 거듭제곱
            dp[i] = 1 + dp[i - offset]

        # 결과 반환: dp 배열
        return dp

 

 

===============================================================================

 

class Solution:
    def countBits(self, n: int) -> List[int]:        
        """
        0 ->   0

        1 ->  01 -> 1
        2 ->  10 -> 1

        3 ->  11 -> 2

        4 -> 100 -> 1
        5 -> 101 -> 2
        6 -> 110 -> 2
        7 -> 111 -> 3

        8 ->1000 -> 1    
        """
        if n == 0:
            return [0]
            
        dp = [0]*(n+1)
        dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i//2] + dp[i%2] 
        return dp

 

class Solution:
    def countBits(self, n: int) -> List[int]:        
        """
        0 ->   0

        1 ->  01 -> 1
        2 ->  10 -> 1

        3 ->  11 -> 2

        4 -> 100 -> 1
        5 -> 101 -> 2
        6 -> 110 -> 2
        7 -> 111 -> 3

        8 ->1000 -> 1    
        """
        # if n == 0:
        #     return [0]

        dp = [0]*(n+1)
        # dp[1] = 1

        for i in range(1, n+1):
            dp[i] = dp[i//2] + i%2
        return dp

 

191 번 활용

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []

        def getBits(num):
            cnt = 0
            while num:
                num &= (num-1)
                cnt+=1
            return cnt

        for i in range(n+1):
            res.append(getBits(i))

        return res

 

https://youtu.be/RyBM56RIWrM?si=sAnUKsuTKn0gekal

 

코드 풀이

class Solution:
    def countBits(self, n: int) -> List[int]:
        """       1개수
        1 - 0001    1 = 1+dp[n-1]
        2 - 0010    1 = 1+dp[n-2]
        3 - 0011    2 = 1+dp[n-2]
        4 - 0100    1 = 1+dp[n-4]
        5 - 0101    2 = 1+dp[n-4] 
        6 - 0110    2 = 1+dp[n-4]
        7 - 0111    3
        8 - 1000    1 = 1+dp[n-8]
        9 - 1001    2
        """
        dp = [0] * (n+1)        
        offset = 1

        for i in range(1, n+1):
            if offset *2 == i:
                offset = i
            dp[i] = 1 + dp[i-offset]
        return dp

 

최종 코드

 

이 문제는 **"0부터 n까지의 모든 정수에 대해, 각각의 이진 표현에서 1의 개수를 구하는 문제"**입니다.

---

✅ 핵심 아이디어 (DP + 비트 연산):

i를 이진수로 표현했을 때의 1의 개수는 다음과 같이 구할 수 있어요:

countBits[i] = countBits[i >> 1] + (i & 1)

• i >> 1은 i를 오른쪽으로 1비트 시프트 → i // 2
• (i & 1)은 i의 마지막 비트가 1인지 여부를 체크

 

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)  # 결과 리스트 초기화 (0부터 n까지)

        for i in range(1, n + 1):  # 1부터 n까지 반복
            ans[i] = ans[i >> 1] + (i & 1)  
            # i // 2의 결과에서 1의 개수 + i의 마지막 비트가 1이면 +1

        return ans  # 완성된 리스트 반환

 

✅ 예시 설명

입력: n = 5 → 결과: [0, 1, 1, 2, 1, 2]

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