[알고리즘] Programmers 2개 이하로 다른 비트 #Python

[Programmers] 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]

---

📍 문제 풀이

📌 처음 접근한 방법

• 짝수의 경우 20 의 자리 즉 1의 값을 나타내는 비트의 자리가 항상 0 이므로 이 값을 1로 바꾸면 x 보다 크고 x와 비트가 1개 다른 조건에 해당하므로 짝수 + 1 의 값을 반환한다.
• 홀수의 경우 주어진 숫자 number 와 number 보다 큰 모든 수를 xor 로 비교하며 비트의 불일치 정도가 2 이하인 값을 반환하는 방법을 수행했다.
• 위 방식은 홀수의 경우에서 너무 많은 반복문을 수행하기 때문에 시간초과가 발생한다.

✍ 코드

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
            continue
        num = number
        while True:
            num += 1
            if bin(number^num).count('1') < 3:
                answer.append(num)
                break
    return answer

📌 새롭게 접근한 방법

• 짝수의 경우는 위와 같고, 홀수의 경우에서 다른 방식을 적용하였다.
  • number 의 값을 2진수로 변환한 후 앞에 '0' 을 추가한다.
  • 변환한 값의 맨 마지막 인덱스(i) 바로 전부터 검사하여 현재 number 의 인덱스의 값이 '0' 일 경우,
    • 현재 인덱스(i) 위치의 값은 '1' 로 바꾸고 그 다음 인덱스 값(i+1)은 '0' 으로 바꾸어 x 보다 크고 x와 비트가 2개 다른 조건에 맞추는 가장 작은 값을 반환한다.

✍ 코드

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