2개 이하로 다른 비트 (lv2)

문제 설명

양의 정수 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

---

 처음에는 number가 최대 10^15까지 나올 수 있으니, 10만번의 순회 동안 이진수로 변환한 문자열의 길이가 최대 15log2(10) = 50 정도로 나올 것이고, 여기서 count로 1의 개수를 세는 탐색을 한다면 최대 50, 이렇게만 봐도 벌써 2500만번의 연산이 소요되지만 혹시나 하고 완전탐색으로 풀어봤다. 당연히 시간초과로 실패한다.

완전탐색

def solution(numbers):
    answer = []
    for i in numbers:
        j = 1
        while format(i ^ i+j,'b').count('1') > 2:
            j += 1
        answer.append(i+j)
    return answer

 따라서 특정한 규칙을 찾을 필요가 있었다. 우선 위 코드로 어떤 규칙이 발견되는지 확인하고자 64 까지 출력해보았는데, carry 비트가 발생할 경우 마지막 인덱스를 기준으로 0이 처음 나타날때까지 연속되는 1은 전부 0이 되므로, 그 자리의 0과 바로 다음인덱스의 1을 각각 뒤집어줌으로써 정답을 받을 수 있었다. 특정 규칙을 발견해야하는 문제는 까다로운듯 싶다.

def solution(numbers):
    answer = []
    for num in numbers:
        b = ['0',*format(num,'b')]
        for i in range(len(b)-1,-1,-1):
            if b[i] == '0':
                if i < len(b)-1:
                    b[i],b[i+1] = '1','0'
                else:
                    b[i] = '1'
                break
        answer.append(int(''.join(b),2))
            
    return answer