[Programmers / JS] 77885번 - 2개 이하로 다른 비트

Problem

문제 보기

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

Solution

function solution(numbers) {
    const result = [];
    
    function convert64Bit(num) {
        const a = num.toString(2);
        const b = '0'.repeat(64 - a.length);
        return b + a;
    }
    
    for (i of numbers) {
        const iNum = convert64Bit(i);
        
        while(true) {
            i++;
            let same = 0;
            const target = convert64Bit(i);
            for(let j = 0; j < target.length; j++){
                if(iNum[j] !== target[j]) same++;
            }
            if(same <= 2) break;
        }
        result.push(i);
    }
    
    return result;
}

10, 11 테스트를 시간 초과로 통과하지 못했다.
 numbers의 수가 10^15이므로 통과하기 힘들었던 거 같다

function solution(numbers) {
    const result = [];
    
    function bit(num) {
        if(num % 2 === 0) return num + 1;
        const a = [...'0' + num.toString(2)];
        const b = a.lastIndexOf('0');
        a.splice(b, 2, '1', '0');
        return parseInt(a.join(''), 2);
    }
    
    for(let i of numbers) result.push(bit(i));
    
    return result;
}

우선 numbers는 10진수로 이루어져있다.

해당 num이 짝수라면 2진수로 변경시 0으로 끝나므로 마지막 0을 1로 바꾼다
그렇다면 num + 1과 값이 같다

해당 num이 홀수라면 2진수로 변경 후에 뒤에서 0이 처음 나오는 부분을 찾아주고 0의 자리에 1로 변경하고 그 바로 뒤 숫자를 1로 바꿔준다. (011 -> 101)

전 코드에서 통과였던 것도 시간 복잡도를 개선한 것을 알 수 있다.