2개 이하로 다른 비트 - 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/77885

 

문제 설명

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

 

문제접근 방식 

• 이문제는 풀때는 마지막 테스트 케이스가 계속 시간 초과가 되어서 답을 확인한 문제입니다.
• 짝수 홀수를 나누어서 규칙을 찾다보면 다음과 같은 패턴이 나오게 됩니다.
• 짝수인 경우 4이라면 이진수로 100 입니다. 4보다 크면서 2개이하로 다른수를 찾으려면 101 입니다. 가장 뒤에 있는 0을 1로 변경하면 됩니다. 
• 홀수인경운 7 이라면 이진수로 0111 (바꿀때는 앞에 0을 붙이는게 편합니다.) 입니다 
• 먼저 짝수의 경우처럼 가장 뒤에 있는 0의 인덱스(idx)를 찾아 1로 변경합니다. 그럼 1111 이 됩니다. 
• 그런다음 idx+1 의 값을 0으로 변경하빈다. 그럼 1011 이 되고 이게 답이 됩니다. 
• 해당 문제를 풀면서 비트에대한 이해를 다시하게 되었으며 bin()이라는 함수로 빠르게 이진수를 만드는게 편한것 같다.

def solution(numbers):
    answer = []
    for num in numbers:
        bin_num = bin(num)
        temp = '0' + bin_num[2:]         
        lastZero = -1
        for i in range(len(temp)):
            if temp[i] == '0':
                lastZero = max(lastZero, i)
        if num%2 ==0:
            answer.append(num+1)
        else:
            result = temp[:lastZero] + '10' + temp[lastZero+2:]
            answer.append(int(result,2))
    return answer

 

문제 해설 링크는 아래에 있습니다 :

https://prgms.tistory.com/57