Counting Bits

Problem

• 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 의 길이의 배열을 반환하는데, 해당 요소들은 0 부터 n+1까지 숫자 Binaray에서 1의 카운트 갯수이다.
• 즉 n에 2이면 [0, 1, 1] 0의 바이너리(0) 1의 갯수 0, 1의 바이너리(1) 1의 갯수 1, 2의 바이너리(10) 1의 갯수 1인 배열을 반환하면 된다.

Solution

BruteForce

• 숫자가 들어오면 바이너리로 변환하여, 1의 갯수를 돌려주는 함수를 만들고 n+1회 루프로 결과값을 배열로 만들어 돌려주는 방법

class Solution:
    def countBits(self, n: int) -> List[int]:
        result = []
        for i in range(n + 1):    
            result.append(self.getBinary(n=i))

        return result

    def getBinary(self, n: int) -> int:
        target = n
        result = []
        while target > 0:
            result.append(target % 2)
            target //= 2
        return result.count(1)

• getBinary 함수를 만들고 %, // 연산으로 바이너리를 값을 구하고 count함수로 1의 갯수를 반환한다.
• countBits 함수는 n+1회 루프를 돌려 getBinary 결과 값으로 배열을 만들어 반환한다.

간단한 수학 공식을 사용한 방법

class Solution:
    def countBits(self, n: int) -> List[int]:
        result = [0] * (n+1)
        print(result)

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

• result 배열을 0을 n+1회 할당하여 만든다.
• 1, n+1회 반복하며 연산된 결과 값을 result 배열에 넣어준다.
• 바이너리의 특성상 2로 나눈 인덱스에 들어있는 바이너리에 나머지 값을 더해주면 1의 갯수를 알수 있기 때문에 해당 연산을 통해 값을 넣어준다.
• 6은(110)은 3(11) + 6%2(0) 이기 때문에 1의 갯수는 2가 된다.
• 7은(111)은 3(11) + 7%2(1) 이기 때문에 1의 갯수는 3이 된다.
• 7 의 바이너리가 가지고 있는 1의 갯수는 7을 2로 나눈 3의 바이너리의 1의 갯수(2) + 7 %2(1) 값이 된다는 의미