문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/77885?language=python3

문제 설명

양의 정수 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
입출력 예

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

문제 풀이

1차 시도

def solution(numbers):
    answer = []
    for number in numbers:
        numTwoBit = bin(number)[2:]
        temp = number + 1
        while True:
            tempTwoBit = bin(temp)[2:]
            sum = 0
            if len(tempTwoBit) != len(numTwoBit):
                numTwoBit = '0' + numTwoBit
            
            for i in range(len(numTwoBit)):
                if numTwoBit[i] != tempTwoBit[i]:
                    sum += 1
                if sum > 2:
                    break
            else:
                answer.append(temp)
                break
            temp += 1
    return answer

맘편하게 브루트 포스로 풀었다가 시간초과 당했다 !

생각해보니까 홀짝으로 나눠 생각할 수 있었다

• 짝수면 끝 비트가 0이니 단순 +1을 해준다
• 홀수라면 끝 비트가 1이니 오른쪽에서 부터 0을 찾아서 1로 바꾸고, 그 바로 뒤는 0으로 바꿔주면, 최소 수가 되는 것을 알수 있다

맞은 코드

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            numTwoBit = '0' + bin(number)[2:]
            idx = numTwoBit.rfind('0')
            st = ""
            for i in range(len(numTwoBit)):
                if i == idx:
                    st += "1"
                elif i == idx+1:
                    st += "0"
                else:
                    st += numTwoBit[i]
            ans = int(st,2)
            answer.append(ans)
            
    return answer