LeetCode [338]: Counting Bits

📌 LeetCode [338]: Counting Bits

🔗 문제 링크

---

문제 설명 📄

정수 n이 주어질 때, 0부터 n까지의 숫자를 2진수로 표현했을 때 1의 개수를 세는 배열을 반환하는 문제입니다.

---

문제 접근 방식 📋

처음에는 각 숫자에서 비트가 1인 개수를 세는 방식으로 접근했습니다. 이를 위해 숫자를 2로 나누면서 나머지를 확인하여, 1이 있는지 확인하고 카운트하는 방법을 사용했습니다.

아이디어 설명 💡

1. countBit() 함수를 정의하여 숫자를 2로 나누며 1의 개수를 세도록 구현했습니다.
2. 0부터 n까지 반복하면서 각 숫자에 대해 countBit() 함수를 호출하고 결과를 answer 리스트에 추가했습니다.

---

Solution 💻

class Solution:
    def countBits(self, n: int) -> List[int]:
        def countBit(n):
            result = 0
            while n > 0:
                if n % 2 == 1:
                    result += 1
                n //= 2
            return result

        answer = []
        for i in range(n + 1):
            answer.append(countBit(i))
        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n log n)
  • 각 숫자 i에서 비트를 세는 데 O(log i)가 소요되고, 이를 n번 반복하므로 총 O(n log n)입니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 결과 배열을 제외하면 고정된 개수의 변수만 사용하므로 O(1)입니다.

---

리팩토링 🛠️

개선된 코드 (동적 계획법 활용)

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

        for i in range(1, n + 1):
            if i % 2 == 0:
                dp[i] = dp[i // 2]
            else:   
                dp[i] = dp[i - 1] + 1

        return dp

리팩토링 후 시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 각 숫자에 대해 상수 시간(O(1))에 결과를 계산할 수 있습니다.
• 공간 복잡도: O(n)
  • dp 배열에 n + 1개의 결과를 저장하므로 공간 복잡도는 O(n)입니다.