프로그래머스 77885 - 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. 해당 하는 수를 2진법으로 바꾼다.
2. 1씩 늘려가며 이진수를 비교한다. 이 때 비교할 때는 xor연산을 사용한다. (같으면 0, 다르면 1)
3. xor 연산을 사용한 후 1의 갯수를 세서 2 이하이면 정답.
4. 2 이상이면 +1

하지만 이 풀이법은 시간초과를 발생시킨다.

from operator import xor

def solution(numbers):
    answer = []

    for number in numbers:
        i = number + 1
        while True:
            tmp = list(format(xor(number, i), 'b'))
            if tmp.count('1') <= 2:
                answer.append(i)
                break
            i += 1

    return answer

 

두번째 방법

가만히 보면 규칙이 보인다.

• 짝수인 경우 : 끝 비트가 무조건 0 => 이 수보다 크고 비트가 1~2개 차이나는 수는 무조건 이 다음 수.
• 홀수인 경우 : 111같이 1만 있는경우 1011 (처음비트를 0으로 바꾸고 앞에 1 추가), 101이면 01->10으로 바꾸기

이러한 규칙이 존재한다.

def count(lst):
    answer = 0
    for i in range(len(lst) -1, -1, -1):
        if lst[i] != '0':
            answer += 1
        else:
            break
    return answer

def solution(numbers):
    answer = []
    
    for number in numbers:
        if number % 2 == 0:
            answer.append(number + 1)
        else:
            tmp = list(format(number, 'b'))
            one_count = count(tmp)
            answer.append(number + (2 ** (one_count - 1)))
    
    return answer