LeetCode [2220]: Minimum Bit Flips to Convert Number

📌 LeetCode [2220]: Minimum Bit Flips to Convert Number

🔗 문제 링크

---

문제 설명 📄

두 정수 start와 goal이 주어졌을 때, start를 goal로 변환하기 위해 뒤집어야 하는 최소 비트 개수를 구하세요.

---

문제 해결 접근 🚀

1. 이진수 변환 및 길이 맞추기:
   • 두 숫자를 이진수로 변환합니다.
   • bin(start)[2:]와 bin(goal)[2:]를 사용하여 이진수 문자열로 변환한 뒤, 짧은 문자열 앞에 0을 채워 길이를 맞춥니다.
2. 비트 비교:
   • 두 이진수 문자열을 순차적으로 비교하여 다른 비트 개수를 세줍니다.
3. 최종 결과:
   • 뒤집어야 하는 비트의 개수를 반환합니다.

---

Solution 💻

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        start = bin(start)[2:]
        goal = bin(goal)[2:]
        more = max(len(start), len(goal))

        start = start.zfill(more)
        goal = goal.zfill(more)

        answer = 0
        for s, g in zip(start, goal):
            if s != g:
                answer += 1

        return answer

---

시간 복잡도 ⏲️

• 이진수 변환 및 길이 맞추기: O(max(len(start), len(goal)))
• 비트 비교: O(max(len(start), len(goal)))
• 총 시간 복잡도: O(n) (여기서 n은 숫자 비트의 최대 길이)

---

공간 복잡도 🗄️

• 이진수 문자열 저장: O(n)
• 결과 저장 변수: O(1)
• 총 공간 복잡도: O(n)

---