[프로그래머스] 2개 이하로 다른 비트 (Python)

👀 다른 사람 풀이

🔗 https://ye0nn.tistory.com/28

def solution(numbers):
    answer = []

    for number in numbers:
        if number % 2 == 0:
            answer.append(number + 1)
            continue

        number_bin = '0' + bin(number)[2:]
        number_bin = number_bin[:number_bin.rindex('0')] + '10' + number_bin[number_bin.rindex('0') + 2:]
        answer.append(int(number_bin, 2))

    return answer

def f(num):
    b_num = "0" + bin(num)[2:]
    if b_num[-1] == "0":
        return num + 1
    else:
        z_idx = b_num.rindex("0")
        n_num = b_num[:z_idx] + "10" + b_num[z_idx + 2:]
        return int(n_num, 2)


def solution(numbers):
    return list(map(f, numbers))

• 처음에는 숫자를 늘려가면서 XOR 연산을 해서 1의 개수로 판단하려고 시도 → 시간 초과
• 문제의 핵심은 서로 다른 비트의 개수가 2개 이하면 되기 때문에 어떻게 바꿀지 판단하는 것
• 숫자가 짝수일 경우
  • 마지막 비트 항상 0
  • 따라서 1을 더하면 무조건 1개의 비트가 다르므로 조건 충족
• 숫자가 홀수일 경우
  • 마지막 비트 항상 1
  • 1을 더할 때 1이 n개 연속되는 형태면 연속되는 개수만큼 0으로 변하고 맨앞 0이 1로 변하면서 총 n+1개의 비트가 다른 수가 됨 (ex. 0111 + 0001 = 1000 → 3개가 연속, 1 더한 후 총 4개의 비트 차이)
  • 따라서 1을 더한 수보다 더 큰 수 중에 차이가 2개 이하인 수를 찾아야 하는데, 이미 맨 앞의 0이 1로 변했기 때문에 나머지 한 자리만 더 다를 수 있음
  • 따라서 처음 연속된 1들 중 가장 앞쪽을 0으로 처리하는게 가능 수들 중 제일 작은 수임 (ex. f(0111) = 1011)
  • 요약하자면 원래 숫자에서 비트 중 우측에서 가장 가까운 0을 찾아 1로 바꾸고, 그 오른쪽 비트를 0으로 바꾼 수가 결과 값이 됨

📚 What I Learned

str.rindex

• 특정 값을 우측부터 탐색해 가장 먼저 일치하는 위치를 반환
• 좌측부터 동일한 기능을 수행하는 str.index 메소드가 있음