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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

풀이

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 함수를 구현하는 문제이다.

구현 문제이기에 우선 간단한 예시를 통해 규칙을 찾아야 한다. 2부터 시작하여 규칙을 찾아보겠다.

2는 이진수로 10이고 2보다 크고 2와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 11로 3이다.

3은 이진수로 11이고 3보다 크고 3과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.

4는 이진수로 100이고 4보다 크고 4와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.

5는 이진수로 101이고 5보다 크고 5와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 110으로 6이다.

6은 이진수로 110이고 6보다 크고 6과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 111으로 7이다.

7은 이진수로 111이고 7보다 크고 7과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 1011으로 11이다.

 

위의 예시들을 살펴보았을 때 찾을 수 있는 규칙은 우선 짝수일 때는 쉽게 찾을 수 있다. 짝수는 이진수로 하였을 때 맨 마지막 자리가 0이므로, 단순하게 맨 마지막 자리의 수를 1로 변경하는 것, 즉 원래 수에 1을 더하는 것으로 답을 구할 수 있다.

어려운 것은 홀수일 때의 규칙을 찾는 것이다. 5의 경우를 살펴보면 101이 110으로 바뀌었기에 처음으로 0인 나온 시점의 다음 비트와 함께 10으로 변경하면 되는 것이 아닌가 의심해 볼 수 있다. 101 -> 110

3도 확인해보면 011 -> 101로 변경되고, 7의 경우에도 0111 -> 1011로 바뀌게 되기에 5의 경우에서 가정한 방법이 옳게 된 가정임을 확인할 수 있다.

 

이제 위에서 찾아낸 방식인 짝수는 1을 더하고, 홀수는 처음으로 0이 나온 경우 그다음 비트와 함께 10으로 변경하는 것을 코드로 구현하면 된다.

def to_binary(number): # 십진수를 이진수로 변환하는 메서드
    binaries = []
    
    while number > 0: # 이진수를 구하려는 숫자를 지속적으로 2로 나누면서 0보다 큰 경우에 반복
        binary = number % 2 # 2로 나눈 나머지를
        binaries.append(str(binary)) # 배열에 저장
        number //= 2 # 2로 나누어 다음 binary 값을 계산할 수 있도록 함
    
    return "".join(binaries[::-1]) # 2로 나눈 나머지들을 역순으로 하면 이는 십진수를 이진수로 변환한 값


def solution(numbers):
    answer = []
    
    for number in numbers:
        if number % 2 == 0: # 숫자가 짝수이면
            answer.append(number + 1) # 단순히 1을 더한 값이 정답
        else: # 숫자가 짝수이면
            bnry = f"0{to_binary(number)}" # 이진수로 변환한 숫자 중
            tgt = bnry.rindex('0') # 첫번째로 0이 나타나는 시점에서
            bnry = f"{bnry[:tgt]}10{bnry[tgt+2:]}" # 그다음 비트와 함께 10으로 변환한 값이
            answer.append(int(bnry, 2)) # 정답
            
    return answer