프로그래머스_2개 이하로 다른 비트

문제

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

코딩테스트 연습 - 2개 이하로 다른 비트

풀이

1. 숫자 n을 2진수로 변환해 m에 저장한다.

10진수 n	2진수 m
26	11010
7	00111

2. m에 0이 있는지 확인한다.

2-1. 0이 없다면(m은 1로만 구성되어 있다.) , 101111....[:size+1] 값을 반환한다.

10진수	2진수	다른 비트수
7	00111
8	01000	4
9	01001	3
10	01010	3
11	01011	2

2-2. 0이 있다면

2-2-1. 0을 1로 치환한다.

가장 작은 수를 구해야 하므로 가장 왼쪽의 0을 선택한다.

index	0	1	2(i)	3	4
2진수 m	1	1	0	1	0
0을 1로 변환	1	1	1	1	0

2-2-2. 1을 0으로 치환한다.

n보다 큰 수여야 하므로 2-2-1에서 선택한 0보다 오른쪽에 있는 1을 선택할 수 없다. (i<j)

11110>01110 (x)

11110>10110 (x)

11110<11100 (o)

가장 작은 수를 구해야 하므로 가능한 왼쪽의  1을 선택한다.

index	0	1	2(i)	3(j)	4
2진수 m	1	1	0	1	0
0을 1로 변환	1	1	1	1	0
1을 0으로 변환	1	1	1	0	0

2-2-3. 10진수로 반환한다.

 

코드

def answer(n):
    m = list(bin(n)[2:])
    size = len(m)

    if m.count('0')==0 : 
        return int(('10'+'1'*size)[:size+1], 2)

    for i in range(size-1, -1, -1):
        if m[i]=='0' :
            m[i] = '1'
            break

    for j in range(i+1, size) :
        if m[j]=='1' :
            m[j] = '0'
            break

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

def solution(numbers):
    return [answer(n) for n in numbers]