[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의 모든 수 ≤  10^(15) ​

입출력 예

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

풀이과정

작은 숫자를 만들기 위해, 최대한 0이 앞에 있고, 1를 뒤로 보내는 것이 가장 중요

1. 최대한 뒤쪽에 위치하는 0 비트를 1로 변경하는 것이 숫자가 작음
   → 총 비트 수는 유지되고 기존 비트가 바뀌는 경우
   
   예를 들어,
   x = 9 (10진수) = 1001 (2진수) 인 경우, 1011로 변경 (뒤쪽에 위치하는 0비트를 1로 변경)
   1011 (2진수) = 11 (10진수), 최종적으로 11로 계산 마무리
   
   그러나 여기서 끝나면 가장 작은 수가 되지 못함
   조건은 2 이하의 비트 수이기 때문에 한 번 더 비트를 수정할 수 있음
   → x보다 크면서 조건을 만족하는 숫자 중 가장 작아야 하기 때문에 수정한 위치 앞쪽 비트는 건드릴 수 X
   ⇒ 수정한 위치 바로 뒷쪽 비트를 0으로 변경
   
   [정답 풀이]
   x = 9 (10진수) = 1001 (2진수)
   1) 1011로 수정 (0비트를 1로 변경)
   2) 1010로 수정 (수정 위치 바로 오른쪽 비트 0으로 변경)
   최종적으로 10으로 계산 마무리
2. 첫 번째 방법이 안될 경우, 1) 새로운 비트(1)가 추가되고, 2) 기존 비트의 가장 앞비트를 0으로 변경
   → 새로운 비트가 추가되고 기존 비트가 변경되는 경우
   
   예를 들어, x = 7 (10진수) = 111 (2진수)
   1) 1111로 수정 (1 추가)
   2) 1011로 수정 (기존의 가장 앞비트 0으로 변경)

정답

def solution(numbers):
    answer = []
    for number in numbers:
        bin_num = list(bin(number)[2:])
        bin_num.reverse()
        for i, digit in enumerate(bin_num):
            if digit == '0':
                bin_num[i] = '1'
                if 0 < i < len(bin_num):
                    bin_num[i-1] = '0'                    
                break
        else:
            bin_num[-1] = "0"
            bin_num.append("1")
        bin_num.reverse()
        answer.append(int("0b"+"".join(bin_num), 2))
    return answer