풀이_2개이하로다른비트.md

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

• Date : 2021.01.09(일)
• Time : 40분

문제 설명

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

  수	비트	다른 비트의 개수
  2	000…0010	0
  3	000…0011	1
  

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

  수	비트	다른 비트의 개수
  7	000…0111	0
  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의 모든 수 ≤ 10^15

예시

• numbers : [2,7]
• result : [3,11]

풀이

def solution(numbers):
    answer = []

    for number in numbers:
        if number % 2 == 0:
            answer.append(number + 1)
        else:
            bin_number = format(number, "b")
            point = bin_number.rfind("01")
            if point == -1:
                bin_number = "10" + bin_number[1:]
                answer.append(int(bin_number, 2))
            else:
                bin_number = bin_number[:point] + "10" + bin_number[point + 2:]
                answer.append(int(bin_number, 2))

    return answer

: 십진수를 이진수로 변환해주기 위해 format(number, "b")를 통해 십진수를 이진수로 바꿔주었다. 처음 조건으로 숫자가 2로 나누어 떨어지면 그냥 +1만 해주었다. 2로 나누어 떨어지는 수는 이진수로 변환했을 때, 0이 항상 존재한다. 그러다 보니 숫자가 1이 커지는 게 가장 최솟값이기 때문에 +1을 한다. 두 번째 조건으로 숫자가 모두 1로만 되어있을 경우이다. rfind는 입력한 문자열이 있다면 그 위치 인덱스를 반환해주고, 없으면 -1을 반환한다. 따라서 rfind("01")이 -1로 나왔을 경우에는 숫자가 모두 1로만 되어있을 경우이다. 숫자가 모두 1로만 되어있다면, 이진수의 자릿수만 늘려주면 된다. 따라서 앞에 "10"을 붙이고, 첫 번째 숫자를 제외한 나머지 숫자들을 뒤에 붙여준다. 이때, 첫 번째 숫자를 지워주는 이유는 0으로 대체했기 때문이다. 또한 "11"이 아닌 이유는 최소 값을 보장해주어야 하기 때문이다. 세 번째 조건으로 위에 두개 모두 아닐 때이다. 그럴 경우 0의 인덱스를 찾아서 그 위치에서만 변화가 일어나면 된다. 예를 들어, "1110111"이라면, "01"을 "10"으로 바꾸는 것이 최소 값을 보장한다. 따라서 앞에 있는 "111"을 그대로 붙이고 "10"을 붙이고 뒤에 "11"을 붙이면 최종적으로 "1111011" 값이 나온다. 최소 값을 보장해주고 비트 변환하는 수가 2개 이하를 보장해준다.