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

https://programmers.co.kr/learn/courses/30/lessons/77885?language=javascript# 

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

function solution(numbers) {
    return numbers.map(v => {
        let str = '0'+v.toString(2);
        if(str[str.length-1] === '0') {
            str = str.substring(0, str.length-1) + '1';
        } else {
            const idx = str.lastIndexOf('01');
            str = str.substring(0,idx) + '10' + str.substring(idx+2, str.length);
        }
        
        return parseInt(str, 2);
    })
}

이 문제는 그냥 진수변환하고 숫자 하나씩 늘려가며 비교하면서 풀면 11번, 12번 시간초과가 무조건! 난다.

 

짝수일때를 생각해보자. 짝수라는건 2진수로 변환했을 때 맨 뒤 숫자가 0일 것이다. ex) 010 => 2, 011 => 3

짝수일 땐 기존 값보다 하나 높인 값이 해당 조건을 만족하는 가장 작은 숫자이다.

 

이제 홀수일 때 생각을 해보자. 홀수일 땐 한 값만 바꾸기엔 값들을 예측할 수 없다. 허나 조건에서 값보다 큰 것중에 찾아야 하므로

뒤부터 '01' 을 찾고 이를 '10'으로 바꿔주면 된다. 뒤부터 찾으며 값을 최소화 할 수 있는 것을 찾아야 하므로, 홀수에선 '01'을 '10'으로 바꾸는 것이 최선이다. ex) 011 => 101 ,  010101 => 010110

 

이를 알고리즘으로 처리하면 위처럼 코드를 작성할 수 있다.