[프로그래머스|파이썬] 2개 이하로 다른 비트(월간 코드 챌린지 시즌2/lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

 

🐍파이썬

❌ 시간초과 실패 코드

def solution(numbers):
    answer = []
    for i in numbers:
        num = bin(i)[2:]
        while True:
            i += 1
            cnt = 0
            num2 = bin(i)
            num = num.zfill(len(num2[2:]))
            for a, b in zip(num, num2[2:]):
                if a != b:
                    cnt += 1
                if cnt > 2:
                    break
            else:
                answer.append(int(num2, 2))
                break
    return answer

정확성: 81.8

합계: 81.8 / 100.0

def solution(numbers):
    answer = []
    for num in numbers:
        numb = list('0'+bin(num)[2:])
        idx = ''.join(numb).rfind('0')	#rfind:오른쪽에서부터 '0'을 찾아 인덱스를 저장
        numb[idx] = '1'
        if num % 2 == 1:
            numb[idx+1] = '0'
        answer.append(int(''.join(numb), 2))	#이진수->십진수
    return answer

numbers에 저장된 수가 짝수인지 홀수인지에 따라 답을 구하는 법이 달라진다.

 

1️⃣ 짝수 (비트를 1개 변경하는 경우)

ex) 4 = 100, 6 = 110, 8 = 1000, ... 👉 무조건 마지막 비트가 0으로 끝난다.

각 숫자에서, 본인보다 크면서 비트가 1~2개 다른 수들 중에서 제일 작은 수는 마지막 0에 1을 더한 수이다. 

예를 들어 6의 경우, 6을 이진수로 바꾸면 110이다. 110보다 크면서 비트가 2개 이하로 다른 수 중 가장 작은 수는 111이다.
따라서 마지막 0을 1로 바꿔주면 답을 구할 수 있다. 

2️⃣ 홀수 (비트를 2개 변경하는 경우)

ex) 5 = 101, 7 = 111, 9 = 1001, 11 = 1011... 👉 무조건 마지막 비트가 1로 끝난다.

짝수와 동일하게 맨 뒤의 0을 1로 바꿀 예정인데, 7의 이진수인 111과 같이 모든 수가 1인 경우를 처리하기 위해 미리 0을 맨 앞에 붙여줘야 한다.

111 -> 0111

이후 0111에서, 짝수에서 진행한 방식으로 가장 뒤에 있는 0을 1로 바꾸어준다.

💡
가장 뒤의 비트를 바꾸어주는 이유는 앞쪽의 비트 0을 1로 바꾸면 그 수는 가장 작은 수가 될 수 없기 때문이다. 예를 들어 1001이 있다고 가정하면, 앞쪽부터 바꿔주는 경우는 1101(=13), 뒤에서부터 바꿔주는 경우는 1011(=11)이 된다.

이렇게 진행하면 0111은 1111이 된다.

비트를 하나 더 바꾸어 가장 작은 수가 되게 만들려면 바꿀 수 있는 비트 중 가장 앞쪽 비트 1을 0으로 바꿔주면 된다. 이전에 1로 바꾼 비트보다 좀 더 낮으면서 제일 높은 자리의 1을 0으로 바꾸면 되므로 이전에 저장해두었던 idx+1위치에 있는 비트를 0으로 바꾸어주면, 1011이 답이 된다.

 

📚 공식 문제 해설 

출처: https://prgms.tistory.com/57

 

 

다른 풀이 방법

def solution(numbers):
    answer = []
    for idx, val in enumerate(numbers):
        answer.append(((val ^ (val+1)) >> 2) +val +1)
    return answer

---

def f(number):
    bin_num = bin(number)[2:]

    if '0' not in bin_num:
        return int('10' + bin_num[1:], 2)

    bin_num = list(bin_num)
    for i in range(len(bin_num)):
        if bin_num[-i-1] == '0':
            bin_num[-i-1] = '1'
            break

    if i > 0:
        bin_num[-i] = '0'

    return int(''.join(bin_num), 2)

def solution(numbers):
    answer = [f(number) for number in numbers]
    return answer