[코딩테스트] 프로그래머스 2개 이하로 다른 비트 파이썬(Python)

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

프로그래머스

from collections import deque
def solution(numbers):

    result = []
    for number in numbers:
        result.append(f(number))
    return result

def f(x):
    if x % 2 == 0:
        return x+1
    else:
        cur = deque(bin(x)[2:])
        nex = deque(bin(x+1)[2:])
        if len(nex)>len(cur):
            cur.appendleft(0)
        for i in range(len(cur)-1,-1, -1):
            if cur[i] == '0':
                break
        cur[i], cur[i+1] = 1, 0
        return int(''.join(map(str, cur)), 2)

문자열의 인덱스 앞쪽(0)에 값을 넣을 때 시간복잡도를 줄이기 위하여

collections의 deque 라이브러리를 사용했습니다.

 

문제를 해결하기 위하여 일정한 규칙을 찾을 수 있었습니다.

 

먼저 입력으로 들어오는 number가 짝수라면 number+1이 number보다 크고 비트가 1~2개 다른 수 중 가장 작은 수로 return이 됩니다.

• 2 : 0010
• 3 : 0011
• 4 : 0100
• 5 : 0101
• 6 : 0110
• 7 : 0111

위 처럼 짝수일 경우에는 가장 마지막인덱스(맨 오른쪽)의 값이 0이 되기 때문에
여기가 1로 바뀌기만 한다면 조건에 부합한 수가 됩니다.

 

홀수일 경우에는 오른쪽부터 즉 len(cur)부터 인덱스 0번까지 값을 확인할 때 가장 먼저 등장한 0을 1로
0의 오른쪽의 있는 1을 0으로 바꾸어준 수가 return이 됩니다.

 

7를 예를 들어보겠습니다.

• 7 : 0111

len([0,1,1,1])부터 인덱스 0번까지 값을 읽을때 인덱스 0번에서 숫자 0이 가장 먼저 등장합니다.

0번 인덱스에 위치한 숫자 0을 1로 바꾸어줍니다.

 

그리고 0번 인덱스의 오른쪽에 있는 1번 인덱스의 1을 0으로 바꾸어주면 1011의 값이 나오게 됩니다.

 

1011을 10진수로 바꾸어준다면 11이 되고 이 값을 return하게 됩니다.

 

코드에서는 bin()함수를 사용하게 되면 0111는 111로 표현되기 때문에

다음 수보다 길이가 짧을 경우에는 앞에 0을 넣어주었습니다.

 

나머지는 위의 설명과 동일합니다.