프로그래머스 2개 이하로 다른 비트

🙂 문제 - 2개 이하로 다른 비트

url : https://programmers.co.kr/learn/courses/30/lessons/77885

✔️ 문제 내용

양의 정수 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 함수를 완성해주세요.

❌ 제한 사항

• 0 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.
• 먼저 주어진 수가 짝수이면 bit는 해당 자리 빼고는 모두 0임으로 +1 ( 1개 변경 )
• 홀수이면 오른쪽 부터 가장 먼저 0이 나오는 수를 1로 변경해주고 1이 나오기 전 수를 0으로 변경 해줍니다. ( 2개 변경 )

• 그렇게 되면 변경 수는 2^n - 2^(n-1)만큼 증가하게 되는 것입니다.
  (n은 처음으로 나오는 0)
  예를 들어 주어진 수가 5라면 이진법으로 변경하였을 때 101이 됩니다.
  그럼 처음으로 0이 나오는 수는 나오는 수 (=n)은 2가 되고 2^2 - 2^1 을 기존 수에 더해준 값이 정답이 됩니다.
  최대 바뀔 수 있는 비트는 2개 임으로 위의 조건이 가능 합니다.

📃 CODE

 def solution(numbers):
   answer = []
   #list(bin(numbers[1]))
   
   for num in numbers:
       if num %2 == 0:
           answer.append(num+1)
       else:
           check= 1
           while True:
               if check & num == 0:
                   break
               check *=2
           answer.append(num+check-check/2)
           #사실 check는 2의 배수이기 때문에 num + check/2 로 해주어도 된다.
   return answer