2개 이하로 다른 비트 - 월간 코드 챌린지 시즌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부터 2진수로 변환하여 찾아나갔다.
1. 맨 마지막 비트가 '0'이라면 '1'로만 바꿔준다. 1개의 비트를 바꿈과 동시에 제일 작은 수가 된다.
2. 맨 마지막 비트가 '1'이라면 '01'로 이루어진 부분을 찾아 '10'으로 바꿔준다. 2개의 비트를 바꾼다.
- 0111 이라면 1011로 바꾼다. f(7) = 11이다.
- 11100010111 이라면 11100011011으로 바꾼다.

3. 11111과 같이 1 비트로만 구성된 경우를 대비하여 모든 비트의 앞에 0을 추가함으로서 01을 찾을 수 있도록 하였다.
   • 011111 -> 101111

문제 풀이

# 2진수 변환
def dec_to_bin(n):
    if n == 0:
        return '0'
    bin = ''
    while n // 2 > 0:
        bin = str(n % 2) + bin
        n = n // 2
        
    return "1" + bin

# 10진수 변환
def bin_to_dec(bin):
    digit = 1
    dec = 0
    for s in reversed(bin):
        if s == '1':
            dec += digit
        digit *= 2
    
    return dec
     
def solution(numbers):
    answer = []

    for number in numbers:
        bin = "0" + dec_to_bin(number)

        if bin == '00':
            answer.append(1)
            continue
        
        if bin[-1] == '0':
            answer.append(bin_to_dec(bin[:len(bin)-1]+'1'))
            continue

        new_bin = ''
        for s in reversed(range(1, len(bin))):
            if bin[s-1:s+1] == "01":
                new_bin = bin[:s-1] + "10" + bin[s+1:]
                break
        
        answer.append(bin_to_dec(new_bin))
                          
    return answer