2개 이하로 다른 비트

프로그래머스

처음에는 number보다 큰 수부터 수를 증가시켜가며 그 수를 이진수로 바꾸고, number와 비교하여 다른 수가 몇개인지 세고, 그 카운트가 2 이하이면 반환하는 방식으로 풀었다.

def solution(numbers):
    result = []
    
    for number in numbers:
        num = format(number, 'b')
        
        for i in range(number+1, number*2):
            cnt = 0
            n = format(i, 'b')
            num = num.zfill(len(n))
            
            for a, b in zip(n, num):
                if a!=b:
                    cnt += 1
                if cnt > 2:
                    break
            if cnt <= 2:
                result.append(i)
                break

    return result

그랬더니 테스트케이스 3개는 틀렸고, 2개는 시간 초과가 떴다.
시간 초과가 떴다는 것은 이 방식으로 푸는게 아니라는 뜻이었고 찾아보니 규칙을 찾아야 했던 문제였다.

def solution(numbers):
    result = []
    
    for number in numbers:
        n = format(number, 'b')
        if number%2 == 0:
            n = n[:-1]+'1'
        else:
            n = '0' + n
            id = n.rfind('0')
            n = list(n)
            n[id] = '1'
            n[id+1] = '0'
            n = ''.join(n)
        result.append(int(n, 2))
       
    return result

• 짝수의 경우 단순히 가장 뒷자리 0을 1로 바꾸어주면 된다.

• 홀수일 경우 제일 앞에 0을 붙이고, 오른쪽에서부터(뒤에서부터) 0을 찾은다음 그 0을 1로 바꾸고 찾은 인덱스+1의 수를 0으로 바꾸면 된다.

  • 오른쪽에서 부터 수를 바꿔야 바꾸기 전의 수와 차이가 적게 난다.
  • rfind(원소) : 오른쪽에서부터 원소를 찾아 그 인덱스를 반환한다. 없으면 -1을 반환한다.