Programmers - 2개 이하로 다른 비트[파이썬(python)]

문제 출처 : 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의 모든 수 ≤ \(10^{15}\)

 

입출력 예

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

 

---

문제 풀이

주어진 수에서 1씩 증가시키며 조건에 맞는 수를 탐색하는 방법으로 풀었다가 시간 초과가 났다.

단순 대입으로 문제를 풀 수 없다면 규칙이 있는지 확인해야한다.

 

만약 주어진 수가 짝수라면 2진수로 표현하였을 때 가장 마지막 비트는 항상 0이다. 그러므로 단순히 주어진 수에 1만 더해준다면 조건을 만족하는 수를 찾을 수 있다.

만약 주어진 수가 홀수라면 2진수로 변환하였을 때 0이 최초로 등장하는 이전 비트에 그 수만큼 더해주면 조건을 만족하는 수를 찾을 수 있다. 이해를 돕기 위해 주어진 수가 11인 경우를 생각해보자.

11은 이진수로 표현하면 1011이다. 그렇다면 11보다 크면서 비트가 1~2개 차이나는 수중 가장 작은 수는 1101로 13이 된다.

1011에서 최초로 나오는 0은 두번째 비트로 2진수에서 4에 해당하는 비트이다. 그 이전 비트는 2에 해당하는 비트이므로 11에 2를 더해주게 되면

1101  +  0010 = 1101으로 조건을 만족하는 수를 찾을 수 있다.

 

구현 코드

코드 링크 : 2개 이하로 다른 비트

def int_to_binary(num):
    arr = []
    while True:
        if num < 2:
            arr.append(num)
            break
        mode = num%2
        arr.append(mode) 
        num = int(num/2)
    arr.append(0)
    return arr

def solution(numbers):
    answer = []
    for num in numbers:
        if num % 2 == 0:
            answer.append(num+1)
        else:
            binary = int_to_binary(num)
            for i, b in enumerate(binary):
                if b == 0:
                    answer.append(num+2**(i-1))
                    break
    return answer