Programmers / 2개 이하로 다른 비트 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 2개 이하로 다른 비트 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def count_different_bits(a, b):
    # XOR 연산을 통해 서로 다른 비트를 찾는다
    xor_result = a ^ b
    
    # XOR 결과에서 1의 개수를 세면 서로 다른 비트의 개수를 구할 수 있다
    different_bits_count = bin(xor_result).count('1')
    
    return different_bits_count

def solution(numbers):
    answer = []
    
    for i in numbers:
        m = i + 1
        # 짝수일 때
        if i % 2 == 0:
            answer.append(i + 1)
        # 홀수일 때
        else:
            while True:
                result = count_different_bits(m, i)
                if result == 2:
                    answer.append(m)
                    break
                else:
                    m += 1
    
    return answer

 

짝수일 때는 항상 2진수 마지막 자리가 0이므로 1만 더해주면 된다. 홀수일때는 xor연산을 통해서 서로 다른 비트의 개수를 구하여 2개가 되면 홀수는 가장 적게 변하면서 큰 수 이므로 그 수를 대입했다.

 

결과 테스트는 통과했지만 문제 조건을 보면 N이 엄청 커질 수록 홀수의 경우에서 시간초과가 나게 된다.

 

그러므로 홀수일 때 처리할 방법을 따로 고안해야한다.

 

def solution(numbers):
    answer = []
    
    for i in numbers:
        # 짝수일 때
        if i % 2 == 0:
            answer.append(i + 1)
        # 홀수일 때
        else:
            num = bin(i)[2:]
            if not '0' in num:
                answer.append(int('10' + num[1:], 2))
            else:
                idx = num.rfind('0')
                answer.append(int(num[:idx] + '10' + num[idx + 2:], 2))
    return answer

print(solution([2, 7]))

 

이 방법은 홀수일때 문제를 해결하는 방법이다.

홀수일 때 2진수로 바꿔서 안에 0이 있는지 없는지 확인한다.

2개 이하로 다른 비트 중 작은 숫자이므로 나중에 1개만 차이가 나는 숫자가 나와도 결과는 상관없다.

ex) 7경우(0이 없음)

7 = 2진수(111)

11 = 2진수(1011)

10 + 11 = 1011

9의 경우

9 = 2진수(1001)

10 = 2진수(1010)

10 + 10 = 1010

---

※ 알아야 할 것

 

format과 bin 둘 다 10진수를 2진수로 바꿀 수 있다.

bin은 대신 앞에 접두사 0b가 붙는다.