(프로그래머스 연습 문제 풀이) 2개 이하로 다른 비트

문제 설명
양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
- x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,
- f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
수           비트          다른 비트의 개수
2          000...0010
3          000...0011              1

- f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
수           비트          다른 비트의 개수
7           000...0111
8           000...1000               4
9           000...1001               3
10          000...1010              3
11          000...1011              2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항
1. 1 ≤ numbers의 길이 ≤ 100,000
2. 0 ≤ numbers의 모든 수 ≤ 1015

입출력 예
numbers      result
[2,7]            [3,11]

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.

def solution(numbers):
    answer = []
    for number in numbers:
        bin_num = list('0' + bin(number)[2:]) # bin() 쓰면 앞에 '0', 'b'가 붙음(ex: 0b100 <- 4)
        idx = ''.join(bin_num).rfind('0') # 0 자리를 오른쪽부터 찾음
        bin_num[idx] = '1'
        
        # 홀수인 경우
        if number % 2 == 1:
            bin_num[idx + 1] = '0'
            
        answer.append(int(''.join(bin_num), 2)) # 2진수를 10진수로
    return answer

(비트 관련 문제만 나오면 왜 어려워보이는건지...) 해당 문제는 비트 연산을 통해 해결하는 문제다. 문제에서 설명하는 규칙은 간단한데, 이를 어떤 규칙을 통해 찾을지가 관건이다. 여기선 짝수와 홀수를 비트로 변환했을 때 어떤 패턴을 가지고 있는지 파악하면 된다.

먼저 짝수의 경우 맨 마지막 비트는 항상 0으로 끝날 것이다. 그러면 해당 숫자보다 크고 비트가 1~2개 다른 수들 중 가장 작은 수는 1만 더해주면 된다. 예를 들어, 10(십진수)은 1010(이진수)로 표현되는데 마지막 0을 1로만 바꿔주면 되는 것이다.

그럼 홀수는 어떨까? 맨 마지막 비트는 항상 1로 끝날 것이며, 다음 비트가 0이면 이것을 1로 바꾸고 1이면 다시 그 다음의 비트를 보면 된다. 즉 오른쪽부터 살펴보며 0이 언제 나오는지 보고 이를 1로 바꾸는 로직이다. 이때 홀수는 자릿수가 바뀌는 것이므로 0만 1로 바꾸면 제일 작은 수가 된다는 것을 보장하지 못한다. 따라서 1로 바꾸는 0의 자리 다음(오른쪽)에 있는 1을 0으로 바꿔주면 된다. 예를 들어, 9(십진수)는 1001(이진수)로 표현되는데, 가장 오른쪽에 있는 0을 1로 바꾸고, 그 오른쪽에 있는 1을 0으로 바꾸면 1010(십진수로 10)이 되며 이것이 가장 작은 수이다.

새롭게 배운 함수는 bin(), rfind(), int(n, 2) 등이 있다. 자주는 쓰지 않는 것 같은데 그리 어렵지 않으니 기억하는 것이 좋을 듯 하다.