[LeetCode][Easy] Count Monobit Integers 문제 Python 풀이

주어진 n에 대하여 0부터 n까지 "0" 혹은 "1"으로만 비트가 구성되어 있는 정수 (Monobit Integer)를 구하는 문제.

 

처음에는 모든 비트가 같아야 한다는 점에 착안, 0부터 n까지 모든 수를 비트 문자열로 만들어 XOR 비트 연산을 수행하여 문제를 해결하도록 구현하였으나 매우 비효율적이었고, 그 후로 

 

초기 방법 (모든 수를 비트 문자열로 생성하여 XOR 연산):

class Solution:
    def countMonobit(self, n: int) -> int:
        if n == 0:
            return 1
        bitified = ["0"]
        for i in range(1, n + 1):
            m = i
            bit = ""
            while m > 0:
                if m % 2 == 1:
                    bit += "1"
                else:
                    bit += "0"
                m //= 2
            bitified.append(bit)

        cnt = 0
        for bit in bitified:
            comp1 = ""; comp2 = ""
            for i in range(len(bit)):
                comp1 += "0"
                comp2 += "1"
            if int(comp1) ^ int(bit) == 0 or int(comp2) ^ int(bit) == 0:
                cnt += 1
        return cnt

 

첫 번째 개선 버전 (n의 비트 길이를 계산하여 그 길이만큼의 Monobit Integers의 경우의 수를 계산하여 답을 반환):

class Solution:
    def countMonobit(self, n: int) -> int:        
        if n == 0:
            return 1
        max_len = 0; tmp = n
        while tmp > 0:
            tmp //= 2
            max_len += 1
        
        bit = ""
        for i in range(max_len):
            bit += "1"
        
        if n < int(bit, 2):
            return max_len
        else:
            return max_len + 1

 

추가 개선 버전 (n의 비트 길이 계산을 python 함수로 해결하고 실제 비트 문자열을 만들지 않고도 해결하도록 개선):

class Solution:
    def countMonobit(self, n: int) -> int:
        if n == 0:
            return 1
        max_len = n.bit_length()
        
        if n < (1 << max_len) - 1:
            return max_len
        else:
            return max_len + 1