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

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

문제 설명

주어진 수보다 큰 수들 중 다음 조건을 만족하는 가장 작은 수 찾기

조건 : 2진법으로 바꿨을 때 1~2자리만 차이가 날 것.

 

풀이 방법

몇 가지 실험을 해보자.

1) 4의 경우, 100 -> 101 뒤의 자리만 바꾸면 된다. 맨 끝이 0이면 1을 하면 된다.

2) 5의 경우, 101 -> 2의 자리의 0을 바꾸고 일의 자리를 줄일 수 있다. 110

3) 11의 경우, 1011 -> 4의 자리를 1로 바꾸고, 그 다음에 2의 자리를 바꾸면 2개 차이가 나고, 가장 숫자 증감을 막았다.

4) 15의 경우, 1111-> 이것의 경우는 16의 자리를 1로 만들고, 증가를 가장 줄일려면 8의 자리를 되돌린다. 10111.

즉, 다음과 같이 푼다.

2진법으로 변형 후, 맨 앞에 0을 붙인다. 그리고 맨 뒤부터 거꾸로 올라가, 최초의 0을 만날댜를 관찰한다.

그 0이 1의자리의 0이면 그냥 그것을 1로 바꾸고, 2의 자리 이상에서 0을 만나면 1로바꾸고 직전의 1을 0으로 바꾼다.

 

def get_answer(num):
    binary_rev = []
    while num > 0:
        binary_rev.append(num % 2)
        num = num // 2
    binary_rev.append(0)
    
    for i in range(len(binary_rev)):
        if i == 0 and binary_rev[i] == 0:
            binary_rev[0] = 1
            break
        elif binary_rev[i] == 0:
            binary_rev[i], binary_rev[i-1] = binary_rev[i-1], binary_rev[i]
            break
    ans = 0
    for j in range(len(binary_rev)):
        ans += binary_rev[j] * (2 ** j)
    return ans

def solution(numbers):
    answer = []
    for num in numbers:
        answer.append(get_answer(num))
    return answer