🔎 2개 이하로 다른 비트

❓ 문제링크

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

📄 제출 코드

function solution(numbers) {
  let answer = [];
  const len = numbers.length;
  for (let t = 0; t < len; t++) {
    let num = numbers[t];
    let bin = num.toString(2);
    if (num % 2 == 0) {
      answer.push(num+1);
    } else {
      bin = bin.split('')
      let idx = 0;
      for (idx = bin.length; idx > 0; idx--) {
        if (bin[idx] == '0') break;
      }
      idx ? bin[idx] = '1' : bin.unshift('1');
      bin[idx + 1] = '0';
      answer.push(parseInt(bin.join(''), 2));
    }
  }
  // var answer = [];
  return answer;
}

처음엔 숫자를 1개씩 증가시키면서 답을 찾으려고 했다. 그러나 testcase10, 11에서 시간초과가 뜬다.

function solution(numbers) {
  let answer = [];
  const len = numbers.length;
  for (let t = 0; t < len; t++) {
    let num = numbers[t];
    let bin = num.toString(2);
    if (num % 2 != 0) {
      answer.push(num);
    } else {
      while (true) {
        num += 1;
        let bin2 = num.toString(2);
    
        if (bin.length != bin2.length) {
          bin = '0' + bin;
        }

        let cnt = 0;
        for (let i = 0; i < bin.length; i++) {
          bin[i] != bin2[i] ? cnt++ : cnt
        }

        if (cnt <= 2) {
          answer.push(num);
          break;
        }
      }
    }
  }
  // var answer = [];
  return answer;
}
let numbers = [4, 7];
console.log(solution(numbers));

다른 방법이 있을까 고민하면서 무작정 써보다가 짝수의 경우 바로 다음 숫자가 정답인게 보였다.

2 10
3 11
4 100
5 101
6 110
7 111
8 1000
...

그러나 여전히 시간초과가 발생했다.
그래서 결국엔 다른 사람의 코드를 참고했다.
짝수의 경우는 예상한대로 다음 숫자가 정답이였다.
홀수의 경우 최하위 비트에서 가장 가까운 0을 찾아서 그 자리의 0을 1로 그다음 비트의 1을 0으로 바꾼다.
최하위 비트에서 멀어질 수 록 더큰 수를 찾는데 n보다 더 크면서 가장 작은 수를 찾기 때문에 최하위 비트에서 가장 가까운 0을 변경한다.

📘 참고

https://www.apexcel.blog/ps/programmers/77885/77885/