[프로그래머스] 2개 이하로 다른 비트 - 자바스크립트

문제

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

 

코드

 

무지성 코드(시간 초과)

function solution(numbers) {
  function f(x) {
    if (x % 2 === 0) return x + 1;
    const bit = x.toString(2);
    let idx = 0;
    let len;
    while (true) {
      len = 0;
      idx++;
      let nextBit = (x + idx).toString(2);
      const diff = nextBit.length - bit.length;
      len +=
        diff +
        nextBit
          .slice(diff)
          .split("")
          .filter((b, i) => b !== bit[i]).length;
      if (len <= 2) return x + idx;
    }
  }
  const answer = [];
  for (let number of numbers) answer.push(f(number));
  return answer;
}

 

정답 코드

function solution(numbers) {
  function f(x) {
    if (x % 2 === 0) return x + 1;
    let bit = "0" + x.toString(2);
    let idx = bit.lastIndexOf("0");
    return parseInt(`${bit.slice(0, idx)}10${bit.slice(idx + 2)}`, 2);
  }
  const answer = [];
  for (let number of numbers) answer.push(f(number));
  return answer;
}

 

풀이

 

우선 무작정 풀이한 코드는 다음과 같다.

 

십진수 x가 짝수라면 이진수로 변경했을 때 0으로 끝나므로, 맨 마지막 0을 1로 바꾼다.
십진우 x가 홀수라면 이진수로 변경해서 숫자를 하나씩 증가시켜가면서 비트가 다른 지점이 2일때까지 반복해봤다.

 

이렇게 단순 비교 방식으로는 문제에서 주어진 테스트케이스 마지막 2개를 통과하지 못했다.

 

풀고나서 제한 사항을 봤다.
당연하게도 numbers의 수가 10^15일 때, 어림도 없는 방법이다.

 

 

정답 코드는 다음과 같다.

 

십진수 x가 짝수라면 이진수로 변경했을 때 0으로 끝나므로, 맨 마지막 0을 1로 바꿔준다.

그러므로 주어진 수 x+1이 정답이다.

 

십진수 x가 홀수라면, x를 이진수로 바꾸고 맨 뒤에서부터 가장 처음으로 나오는 0을 찾아주고,
0의 바로 전 자리에서 1을 더해준다 생각하면, 0을 1로 바꾸고 바로 전 자리의 1을 0으로 바꿔준다.

 

 

예를 들면

x=3일 때, 11(2) 이므로 0을 찾지 못한다.

변환한 이진수의 맨 앞에 숫자 0을 붙여서 시작한다.(이게 싫다면 0이 있을 때, 없을 때를 if/else로 구분 해도 OK.)

 

그러므로 011(2)에서부터 시작해주겠다.
처음 0이 발견되었다면 0=>1로 바꿔주고, 발견된 0의 바로 뒷 자릿수인 1을 1=>0으로 바꾼다.

 

이진수 011는 101이 되고, 101의 십진수 5가 정답이다.

 

이 알고리즘을 그대로 구현한 것이 정답 코드이다.

 

 

정답을 바탕으로  x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 는

비트가 1개 다르면 짝수, 비트가 2개 다르면 홀수 일 것임을 알 수 있었다.