leetcode medium : Minimize XOR

https://leetcode.com/problems/minimize-xor/

 

굉장히 까다로웠다.

일단 num2에 1이 몇 개 있는지를 세는 것부터 시작한다.

그리고 num1의 큰 자릿수 부터 1을 채워가며 x를 찾는다. 그래야 xor할때 제일 작아지니까.

문제는 num1과 num2의 1의 개수가 다른 경우인데

이거때문에 두 숫자의 1 개수의 mininum을 구해서 그만큼 앞에서부터 채우고

num2가 1이 더 많아서 남는 경우엔 뒤에서부터 채우는 방법을 썼다.

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        def count(num):
            if num == 0: return 0
            return num % 2 + count(num//2)
        
        numOfSetBits = count(num2)
        
        lst = []
        i = 0
        tmp = num1
        while tmp:
            if tmp % 2:
                lst.append(i)
            tmp //= 2
            i += 1
            
        x = 0
        for i in range(1, min(len(lst), numOfSetBits) + 1):
            x += 2**lst[-i]
        
        p = 0
        for i in range(numOfSetBits-len(lst)):
            while 2**p & num1 != 0:
                p += 1
            x += 2**p
            p += 1
        
        return x

코드는 굉장히 지저분쓰 하지만

성능은 나쁘지 않게 나왔다.

 

근데 discussion 들어가보고 깜짝 놀라고 말았다.

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        a, b = num1.bit_count(), num2.bit_count()
        res = num1
        for i in range(32):
            if a > b and (1 << i) & num1 > 0:
                res ^= 1 << i
                a -= 1
            if a < b and (1 << i) & num1 == 0:
                res ^= 1 << i
                a += 1
        return res

일단 int클래스에 bit_count 메서드라는게 있는것부터 처음 알았다.

이분은 result를 num1으로 먼저  초기화해놓고 num1의 1의개수(a)와 num2의 1의개수(b)를 비교해서 num1이 더 많으면 그만큼 작은 자리수에서부터 1을 빼고 (앞에서부터 채우는게 아니라 뒤에서 빼는걸로.. 반대로 하셨다.) num2가 더 많으면 1을 채워나가는걸로 하셨다. 근데 이게 두 숫자의 1의 개수를 비교해가면서 원스캔으로 할 수 있는건지는 전혀 몰랐다. 대단하다..