[알고리즘] 2개 이하로 다른 비트

문제 설명

 

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

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

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수비트다른 비트의 개수

7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

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

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

입출력 예

numbers	result
[2,7]	[3,11]

나의 풀이

const numbers = [2, 7];

// 7
// 3 1
// 1 1

// 9
// 4 1
// 2 0
// 1 0

// 10
// 5 0
// 2 1
// 1 0
// 0 1

const Change = {
  0: "1",
  1: "0",
};

function loop(binary, arr, index, cnt) {
  if (cnt === 2) {
    return;
  }
  for (let i = index; i < binary.length; i++) {
    const str = binary.map((data, idx) => (idx === i ? Change[data] : data));

    arr.push(parseInt(str.join(""), 2));

    loop(str, arr, i, cnt + 1);
  }
}

function solution(numbers) {
  var answer = [];

  for (let i = 0; i < numbers.length; i++) {
    const num = numbers[i];
    const arr = [];

    let beatNum = num.toString(2);

    for (let j = 0; j < (beatNum.length % 4) + 1; j++) {
      beatNum = "0" + beatNum;
    }

    loop(beatNum.split(""), arr, 0, 0);
    answer.push(arr.filter((data) => num < data).sort((a, b) => a - b)[0]);
  }
  return answer;
}

console.log(solution(numbers));

 

최초에는 2개만 다른 가능성이 있는 모든 비트를 만들어서 계산을 했다. 

하지만 작동 시간이 길어져서 다시 작업하였다. 

 

const numbers = [2, 7];

// 7
// 3 1
// 1 1

// 9
// 4 1
// 2 0
// 1 0

// 10
// 5 0
// 2 1
// 1 0
// 0 1

function solution(numbers) {
  var answer = [];

  for (let i = 0; i < numbers.length; i++) {
    const num = numbers[i];
    let nextNum = num + 1;

    let beatNum = num.toString(2);

    while (true) {
      let nextBeatNum = nextNum.toString(2);

      if (beatNum.length < nextBeatNum.length) {
        beatNum = "0" + num.toString(2);
      }

      const check = nextBeatNum
        .split("")
        .filter((data, idx) => beatNum[idx] !== data).length;

      if (check <= 2) {
        answer.push(nextNum);
        break;
      }
      nextNum++;
    }
  }
  return answer;
}

console.log(solution(numbers));

2번째로는 + 1을 시켜주면서 2개 이상 다른 경우를 계산했다. 

속도는 전에 비해서 빨라졌지만 여전히 시간은 오래걸렸다.

 

const numbers = [4, 5];

// 7
// 3 1
// 1 1

// 9
// 4 1
// 2 0
// 1 0

// 10
// 5 0
// 2 1
// 1 0
// 0 1
function solution(numbers) {
  var answer = [];

  for (let i = 0; i < numbers.length; i++) {
    const num = numbers[i];
    const binary = num.toString(2).split("0");

    answer.push(num + Math.round(2 ** (binary[binary.length - 1].length - 1)));
  }
  return answer;
}

console.log(solution(numbers));

공식이 있다는걸 알았다는데, 

숫자 + (2 ** (0을 만나기전 반복되는 1의 갯수 - 1)

0을 만나기전 반복되는 1의 갯수란 110111이라면 111로 즉, 3이 된다. 

 

만약 짝수의 경우 마지막이 0으로 끝나서 (0을 만나기전 반복되는 1의 갯수 - 1)이게 -1이 된다. 

2 ** -1은 0.5가 되기 때문에 이것을 반올림처리를 한다면 1이 되서 + 1로 제대로된 답이 나온다.