LeetCode [191]: Number of 1 Bits

📌 LeetCode [191]: Number of 1 Bits

🔗 문제 링크

---

문제 설명 📄

주어진 양의 정수 n의 2진수 표현에서 1의 개수를 세는 문제입니다.

---

문제 접근 방식 📋

처음에는 n을 2로 나누면서 나머지가 1일 때마다 카운트를 증가시키는 방식으로 접근했습니다.

아이디어 설명 💡

• 각 비트를 하나씩 확인하기 위해 n % 2를 사용했습니다.
• n을 2로 나누는 방식으로 오른쪽으로 비트 시프트하며 1의 개수를 세어 나갔습니다.

---

Solution 💻

class Solution:
    def hammingWeight(self, n: int) -> int:
        answer = 0
        while n > 0:
            if n % 2 == 1: 
                answer += 1
            n //= 2  
        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(log n)
  • n을 2로 나누면서 이진수의 길이만큼 반복하므로 O(log n)입니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 추가 메모리를 사용하지 않습니다.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n > 0:
            n &= (n - 1)  # 가장 오른쪽에 있는 1을 제거
            count += 1
        return count

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

• 시간 복잡도: O(k)
  • k는 n의 이진수 표현에서 1의 개수입니다. 1의 개수만큼만 반복하기 때문에 더 효율적입니다.

리팩토링 후 공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 추가 메모리를 사용하지 않습니다.