[LeetCode OJ] Bitwise AND of Numbers Range - Medium Algorithm

<Problem Link>


<Comment>

자, 이번에도 이진수를 다루는 문제가 나왔다.

지난번에 파이썬의 이진수를 다루는 문제가 나왔으므로 이진수와 십진수를 왔다갔다 하는 것에 대한 것은 이제 쉽다!
다만, 이것은 이진수의 성질을 조금 이해해야 쉽게 풀수가 있기에 Medium레벨이 아닌가 싶은 생각이 든다.

이진수가 작은값에서 큰값으로 linear 하게 1씩 증가하는 상황이라면
이진수의 특정 position의 값이 0에서 1로 변하기 위해서, 그 보다 낮은 자릿수의 숫자들이 모두 최소 1번이상 0,1의 두 값을 모두 취해야 한다.

예를 들자면 5의 이진수는 101 이고, 8의 이진수는 1000 이다.
101에서 1000으로 순차적으로 1씩 증가하며 숫자를 나열해보면 

101 > 110 > 111 > 1000     이 된다.

즉 2의 3승 자릿수가 0에서 1이 되기위해 그 보다 낮은 자릿수는 모두 0 과 1을 체험?해야만 하는것이다.

내가 무슨말을 하는지 알았다면 이문제를 쉽게 해결할 수 있을것이다 ㅋㅋ

<Useful Code>

이진수가 나왔으니 망정인데~~~
파이썬에서 이진수, 8진수, 16진수를 표현하는 방법이 있다.!!
파이썬 콘솔을 키고 아래의 3가지 를 입력해보자

0b10
010
0x10

자, 이것은 시스템상으로 약속이 되어있는 것인데, 숫자 앞의 이니셜이 무엇이 오느냐에따라
컴파일러는 해당 숫자가 어떤 '진법'으로 표기된 숫자인지 인식하게 된다.

그리하여,
0b{이진수} 
0{8진수}
0x{16진수}
를 의미하는 것이다 !!

<Solution> Python - Accepted

================================================
실행시간 : 189ms
시간복잡도 : O(N)
공간복잡도 : O(1)
================================================

class Solution:
    # @param m, an integer
    # @param n, an integer
    # @return an integer
    def rangeBitwiseAnd(self, m, n):
        bm = bin(m)[2:]
        bn = bin(n)[2:]
        lm = len(bm)
        ln = len(bn)

        if lm != ln:  # 이진수의 자릿수가 다르면 연산할 필요도 없음
            return 0

        ret = ""
        bit_changed = False
        for i in range(0, lm):
            m_bit = bm[i]
            n_bit = bn[i]

            if bit_changed:  # 한번 자릿수가 변경되 이후로는 쭉 '0'을 넣어준다.
                ret += "0"
            else:
                if m_bit != n_bit:
                    bit_changed = True
                    ret += "0"
                else:
                    ret += m_bit

        return int(ret,2)



통계 위젯 (블랙)

6221
1191
243249

GoogleAdsenseResponsive

Cluster map