[프로그래머스] 2개 이하로 다른 비트 #파이썬 #xor #비트 [월간 코드 챌린지 시즌2]

https://programmers.co.kr/learn/courses/30/lessons/77885#

코딩테스트 연습 - 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의 모든 수 ≤ 1015

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

풀이

처음 이 문제를 마주한 순간, 값을 1씩 증가시키며 이진화하여 값이 다른 비트의 수를 전수 조사하기 쉽습니다. 이렇게 되면 시간 초과에 걸리며, 문제의 함정에 빠져 시간을 낭비하게 됩니다. 구체적인 구현 방식을 언급하지 않는 이러한 문제는, 입출력의 패턴을 먼저 조사하는 행동이 필요합니다.

수	비트	result
0	000...00000	000...0001
1	000...00001	000...0010
2	000...00010	000...0011
3	000...00011	000...0101
4	000...00100	000...0101
5	000...00101	000...0110
6	000...00110	000...0111
7	000...00111	000...1011
8	000...01000	000...1001
9	000...01001	000...1010
10	000...01010	000...1011
11	000...01011	000...1101
12	000...01100	000...1101
13	000...01101	000...1110
14	000...01110	000...1111
15	000...01111	000...10111
16	000...10000	000...10001

이제 비트가 변화하는 패턴을 살펴봅시다.

00부분은 01로, 01은 10으로, 10은 11로 변화하는 것을 볼 수 있습니다. 이진수로 변환한 뒤, 11이 아닌 부분을 찾아 변경하고, 다시 십진수로 변환하는 코드입니다.

def solution(numbers):
    answer = []
    for div in numbers:
        if div < 2:
            answer.append(div+1)
            continue

        binary = []    
        while div:
            div, mod = divmod(div, 2)
            binary.append(mod)
            
        for i in range(len(binary)-1):
            if binary[i:i+2] == [0, 0] or binary[i:i+2] == [0, 1]:
                binary[i] = 1
                break

            if binary[i:i+2] == [1, 0]:
                binary[i:i+2] = [0, 1]
                break
        else:
            binary[-1] = 0
            binary.append(1)

        base10 = 0
        for i in range(len(binary)):
            base10 += binary[i] * 2 ** i
        answer.append(base10)
    return answer