[프로그래머스] 2개 이하로 다른 비트 - python

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 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

풀이

처음에는 이진수로 변환해서 하나씩 비교하는 방식으로 했는데 시간 초과가 났다.

찾아보니 쉬운 방식이 있었다.

• 짝수의 경우 : 항상 0으로 끝난다. 마지막을 1로 바꿔주면됨
• 홀수의 경우 : 마지막으로 나오는 0을 1로 바꾸고 그 옆의 1을 0으로 바꿔준다.

from collections import Counter
​
def solution(numbers):
    answer = []
    for number in numbers:
        binary = list('0'+bin(number)[2:])
        idx = ''.join(binary).rfind('0')
        binary[idx] = '1'
        if number % 2 == 1:
            binary[idx + 1] = '0'
        answer.append(int(''.join(binary), 2))
    return answer

rfind는 오른쪽부터 특정 문자의 위치를 찾는 함수이다.