Level 2 ) 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]

풀이

1. numbers의 각 숫자를 이진수로 변환한다.
2. 주어진 숫자보다 큰 숫자(num)를 이진수로 변환해 각 자릿수를 비교한다.
3. 자릿수가 다른게 2보다 크면 num을 증가시켜 다시 비교한다.
4. 자릿수가 다른게 2 이하면 answer에 담아준다.

-> 테스트케이스 2개에서 시간 초과가 발생했다.

function solution(numbers) {
    let answer = [];
    for(let i=0;i<numbers.length;i++){
        let bit = numbers[i].toString(2); // 이진수 변환
        let num = numbers[i] + 1; // x보다 큰 수
        while(true){
            let f = 0; // 자릿수 다른 갯수
            let bit_num = num.toString(2); // x보다 큰 수를 이진수 변환
            // 길이 다를 수 있으므로 맞춰주기 
            if(bit.length > bit_num.length){
                bit_num = '0'.repeat(bit.length - bit_num.length) + bit_num
            }else if(bit.length < bit_num.length){
                bit = '0'.repeat(bit_num.length - bit.length) + bit
            }
            for(let j=0;j<bit.length;j++){
                if(bit[j] !== bit_num[j]) f++; // 자릿수 다르면 카운트 증가
                if(f > 2){
                    num++;
                    continue; // 다른 자릿수가 2보다 크면 num증가시켜서 진행
                }
            }
            if(f <= 2){
                answer.push(num);
                break; // 2보다 같거나 작으면 answer에 담기
            }
        }
    }
    return answer;
}

시간 초과 안나는 풀이

• 주어진 수가 짝수면 이진수로 변환했을 때 일의 자리수가 무조건 0이므로 마지막 0을 1로 바꾼 수가 가장 작은 수이다.(즉, 주어진 수 + 1이 답이다.)
• 주어진 수가 홀수면 이진수로 변환했을 때 가장 마지막으로 나오는 0을 찾아 1로 바꾸고, 바로 뒤에 나오는 1을 0으로 바꾸어 준다.
  (만약 0이 나오지 않을 경우 맨 앞에 0을 붙여서 구해준다.)
  ex. 3 -> "11" -> "011" -> "101"

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;
}

https://gobae.tistory.com/76