[Python] 2429. Minimize XOR

난이도 : Medium

 

x라는 수는 num2와 bit 수가 같고, x XOR num1이 최소값인 값을 찾는 문제

 

즉, 비트 연산을 해야하는 문제

 

num1과 num2의 범위는 10^9였고, 2진수로 나타내면 '111011100110101100101000000000(2)'. 얼추 30자리 정도 된다.

range는 넉넉잡아 31 정도로 setting하고, 다음과 같이 풀었다.

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        a = num1.bit_count()
        b = num2.bit_count()
        ans = 0

        if a == b:
            return num1

        for i in range(30, -1, -1):
            if b > 0 and (num1 & (1 << i)): #b가 0보다 크고, num1의 i번째 비트가 1이면
                ans |= (1 << i)             #ans의 i번째 비트를 1로 설정
#               print(bin(1 << i), bin(ans))
                b -= 1
        for i in range(31):
            if b > 0 and not (ans & (1 << i)): #b가 0보다 크고, ans의 i번째 비트가 1이면
                ans |= (1 << i)				   #ans의 i번째 비트를 1로 설정
#               print(bin(1 << i), bin(ans))
                b -= 1
        
        return ans

사실, 이 문제는 직관적으로 이해되지 않아서 많은 해답들을 참고하였다.

num2의 bit 수(b)가 0보다 크고, num1의 i번째 비트가 1이라면 ans를 바꿔버리는 것

 

예시 중 num1 = 99, num2 = 63인 case가 있었다.

99를 2진법으로 표현하면 1100011이 된다.

63을 2진법으로 표현하면 111111. 즉 1이 6개인 숫자를 가지되 XOR 값이 최소인 case를 찾아야 함

 

먼저 역순 for문을 돌았을 때의 i와 ans

 

6 1000000

5 1100000

1 1100010

0 1100011

 

1이 6개가 아닌 4개인 상황 (2개 부족)

그 다음 for문을 거쳤을 때의 i와 ans

 

2 1100111

3 1101111

 

비트 연산 문제는 처음 풀어봤는데(비전공자 쉴드...), 아직은 친해지기 어렵다. 좀 더 노력하자..

 

Rumtime : 0ms

Memory : 17.74MB (68.42%)