[Javascript] 2개 이하로 다른 비트 (77885)

문제링크

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

 

접근 방법

처음에는 두 binary 문자열을 비교하여 1의 개수 차이를 반환하는 함수를 만들어
주어진 number을 1씩 증가하며 number과 비교하는 방식으로 접근하였다.

하지만 범위가 ( 1 ≤ numbers의 길이 ≤ 100,000 ),  ( 0 ≤ numbers의 모든 수 ≤ 10^15 ) 으로 매우 넓어 이렇게 접근하면 효율성에서 탈락하게 된다.

그래서 다른 아이디어로 접근하였다.

1. binary의 가장 뒤가 0인 경우
11000, 11100, ... 이런 경우는 그냥 +1을 하면 정답이 된다.

if(binary[binary.length - 1] === "0") answer.push(number+1)​

2. binary의 가장 뒤가 0이 아닌 경우
100111, 111111, 111011 ... 이런 경우는 패턴이 있다.

우선 +1을 적용하고 비트수의 차이가 2이 되도록 만들면
1. 100111(기존 비교할 num) -> 101000 -> 101011(비트수가 2개 차이)
2. 0111111(기존 비교할 num) -> 1000000 -> 1011111(비트수가 2개 차이)
3. 111011(기존 비교할 num) -> 111100 -> 111101(비트수가 2개 차이)

이제 패턴이 보인다.
1. 은 뒤에서부터 연속된 1의 수가 3개였을때, 2개가 되었고
2. 도 뒤에서부터 연속된 1의 수가 6개였을때, 5개가 되었고
3. 도 마찬가지로 뒤에서부터 연속된 1의 수가 2개였을때, 1개가 되었다.

1111 같이 뒤에서부터 연속된 비트수를 10진법으로 바꾸기 위해선 연속된 1의 개수 (n)일때
2^n - 1 이되고, 앞선 과정(1. 2. 3.)에서 중간에 +1을 하였으므로

결국 (기존 비교할 num)을 2진법으로 만들어 뒤에서부터 연속된 1의 수를 찾아 
(연속된 1의 수 - 1) ^ 2 을 더해주면 된다. 

else{
    const oneCnt = findConsecutive1S(binary)
    answer.push(number + (2 ** (oneCnt-1)))
}

// 뒤에서부터 연속된 1의 개수를 찾아 반환
const findConsecutive1S = (str) => {
    let cnt = 0;
    let endIdx = str.length - 1;
    while(str[endIdx] === "1"){
        endIdx--;
        cnt++;
    }
    return cnt;
}

function solution(numbers) {
    var answer = [];
    
    numbers.forEach(number => {
        const binary = number.toString(2);
        
        if(binary[binary.length - 1] === "0") answer.push(number+1)
        else{
            const oneCnt = findConsecutive1S(binary)
            answer.push(number + (2 ** (oneCnt-1)))
        }
    })
    
    return answer;
}

const findConsecutive1S = (str) => {
    let cnt = 0;
    let endIdx = str.length - 1;
    while(str[endIdx] === "1"){
        endIdx--;
        cnt++;
    }
    return cnt;
}