LeetCode [476]: Number Complement

📌 LeetCode [476]: Number Complement

🔗 문제 링크

---

문제 설명 📄

양의 정수 num이 주어졌을 때, 해당 숫자의 2진수 표현에서 모든 비트를 반전시켜서 반환하는 문제입니다.
반전된 숫자는 동일한 비트 길이를 가져야 합니다.

---

Solution 💻

class Solution:
    def findComplement(self, num: int) -> int:
        answer = []

        while num != 0:
            answer.append(num % 2)
            num //= 2

        for i in range(len(answer)):
            if answer[i] == 0:
                answer[i] = 1
            else:
                answer[i] = 0

        result = 0
        for i in range(len(answer)):
            if answer[i] == 1:
                result += 2**i

        return result

시간 복잡도 분석 ⏲️

• 이진수 변환: while 루프를 통해 (O(log n)).
• Complement 계산: (O(log n)), 비트를 뒤집음.
• 결과 계산: 각 비트를 처리하며 (O(log n)).
• 최종 시간 복잡도: (O(log n)).

공간 복잡도 분석 🗄️

• 리스트 answer: (O(log n)), 숫자의 비트 길이에 따라 저장.
• 총 공간 복잡도: (O(log n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def findComplement(self, num: int) -> int:
        bit_length = num.bit_length()  
        all_ones = (1 << bit_length) - 1  
        return num ^ all_ones

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

• 비트 연산:
  • 비트 길이 계산: (O(1)).
  • 마스크 생성: (O(1)).
  • XOR 연산: (O(1)).
• 최종 시간 복잡도: (O(1)).

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

• 상수 공간 사용: (O(1)).

---