[프로그래머스] Lv2. 2개 이하로 다른 비트 😑

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

---

입출력 예numbersresult

[2,7]

[3,11]

처음 풀이 (잘못된 풀이)

def solution(numbers):
    answer = []
    for num1 in numbers:
        bin_num1 = bin(num1)[2:]
        num2 = num1
        while True:
            cnt = 0
            num2 += 1
            bin_num2 = bin(num2)[2:]
            length = len(bin_num2)
            bin_num1 = bin_num1.rjust(length, '0')
            for n1, n2 in zip(bin_num1, bin_num2):
                if cnt > 2:
                    break
                if n1 != n2:
                    cnt += 1    
            if cnt <= 2:
                answer.append(num2)
                break
            else:
                continue
    return answer

테스트 10과 테스트 11에서 시간 초과가 난다.

 

정답 풀이

f(3) = 5
3 => 101
5 => 101

f(5) = 6
5 => 101
6 => 110

f(7) = 11
7 => 111
11 => 1011

f(9) = 10
9 => 1001
10 => 1010

이렇게 홀수일 때 규칙을 찾을 수 있다.

홀수일때는 뒤에서부터 탐색했을 때 처음 만난 0을 1로 바꾸고 바로 다음 비트에 있는 것을 0으로 바꾸면 된다.

짝수일때는 가장 끝의 비트를 1로 바꾸면 되는 것이라 +1만 하면 된다.

그런데 7처럼 모든 비트가 1이면 0의 위치를 찾을 수 없기 때문에 홀수일 경우에는 맨 앞에 0이 붙도록 한다. 

def solution(numbers):
    answer = []
    for num in numbers:
        if num % 2 == 0: #짝수
            answer.append(num + 1)
        else: #홀수
            bin_num = list('0' + bin(num)[2:])
            for i in range(len(bin_num) - 1, -1, -1):
                if bin_num[i] == '0':
                    bin_num[i] = '1'
                    if i + 1 < len(bin_num):
                        bin_num[i + 1] = '0'
                        break
            answer.append(int(''.join(bin_num), 2))
    return answer