[Programmers] 2개 이하로 다른 비트 (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
문제 예시와 같습니다.

문제 풀이

처음 문제를 보자마자 당연히 xor 비트연산자로 푸는 문제라고 생각해 풀었는데 테스트케이스 10,11에서 시간초과가 떴다. 테스트 케이스의 값의 크기들이 커서 시간초과가 중요한 문제 인줄은 알았지만, 비트 연산자가 내 생각보다 시간복잡도를 많이 잡아 먹는다는걸 알게되었다.

어쨌든 그래서 문제를 풀기위해 숫자를 하나하나 증가시켜가면서 어떻게 해야 비트가 2개이하인 가장 작은수를 찾을 수 있는지 노트에 써보았는데,
이렇게 구현방식을 정확하게 했음에도 풀리지 않는 문제는, 특이한 패턴이 있어 그 패턴을 찾아 구현하면 통과 된다는 것을 깨달았다.

이 문제는 비트가 2개 이하로 다르면서 가장 작은 수를 구하는 패턴을 찾아야 하는데, 짝수일 경우는 끝이 0이기 때문에 1하나만 바꿔주면 바로 다음 작은수가 된다. 따라서 짝수일때는 해당 숫자 +1을 답으로 저장해주면되고, 혹수일 경우는 오른쪽에서부터 0을 찾아서 그 값을 1로 바꾼뒤 그 다음인덱스를 0으로 바꿔주면 답이나온다.

코드

def solution(numbers):
    answer = []
    for number in numbers:
        if number%2 == 0:
            answer.append(number+1)
        else:
            bin_num = list('0' + bin(number)[2:])
            idx = ''.join(bin_num).rfind('0')
            bin_num[idx] = '1'
            bin_num[idx+1] = '0'
            answer.append(int(''.join(bin_num),2))
        
    return answer

solution([2,7])

[3, 11]

노트

역시 풀이를 보니까 너무나 간단한 풀이가 있었는데, 이번거는 좀 놀랐다…
너무 간단하게 풀었기 때문인데, 사실 저 패턴을 짧은시간에 직관적으로 찾아내는건 말이 안되는 것 같다.

아래에 코드 첨부한다.

def solution(numbers):
    answer = []
    for idx, val in enumerate(numbers):
        answer.append(((val ^ (val+1)) >> 2) +val +1)

    return answer