[프로그래머스]2개 이하로 다른 비트

문제링크
https://programmers.co.kr/learn/courses/30/lessons/77885

문제 설명

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

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

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

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

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

제한사항

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

입출력 예

문제풀이

1. number의 요소가 0이라면 1을 넣어준다.
2. 아니라면 1을 더한 수가 2의 제곱인지 확인한다. 2의 제곱이면 현재 요소와 현재 요소의 1을 더한 수를 2로 나눈 수를 더해서 answer에 넣어준다.
3. 아니라면 v가 짝수인지 확인한다 짝수면 1 더한 수를 answer에 넣어준다.
4. 아니라면 요소를 2진법으로 변환한 후 마지막으로 나온 0의 인덱스에 두 수를 삭제하고 '10'으로 변환하고 answer에 넣어준다.

코드

function solution(numbers) {
    var answer = [];
    numbers.map(v => {
        if(v==0) answer.push(1);
        else{
            if(isPowOfTw(v+1)) answer.push(BigInt(v+((v+1)/2)));
            else{
                let powTo = v.toString(2);
                let idx = powTo.lastIndexOf(0);
                if(v%2==0) answer.push(BigInt(v+1));
                else{
                    powTo = powTo.substring(0, idx) + "10" + powTo.substring(idx+2);
                    answer.push(BigInt(parseInt(powTo,2)));
                }
            }
        }
    })
    return answer;
}
function isPowOfTw(n){
    return !(n&(n-1));
}

이렇게 했는데 10,11번만 통과를 못했다ㅠㅠ반례를 못찾겠다ㅠㅠ

다른사람 코드

function solution(numbers) {
    var answer = [];
    numbers.forEach(v => {
        if(v%2==0) answer.push(v+1);
        else{
            let str = "0"+v.toString(2);
            for(let i=str.length; i>=0; i--){
                if(str[i]=='0'){
                    answer.push(parseInt(str.substring(0,i)+"10"+str.substring(i+2),2));
                    break;
                }
            }
        }
    })
    return answer;
}

홀수,짝수로 나누고 홀수이면 1만 있는 경우가 있기 때문에 처음 0을 붙여줘서 0의 인덱스를 찾아준다. 0을 찾으면 해당 문자열을 앞뒤로 자르고 중간에 "10"을 넣어준다. bigInt의 문제인줄 알았는데 아니었다ㅠㅠ

리팩토링

function solution(numbers) {
    var answer = [];
    numbers.map(v => {
        if(v%2==0) answer.push(v+1);
        else{
            let str = "0" + v.toString(2);
            let idx = str.lastIndexOf(0);
            str = str.substring(0, idx) + "10" + str.substring(idx+2);
            answer.push(parseInt(str, 2));
        }
    })
    return answer;
}

TIL

• BigInt : 아주 큰 숫자를 처리할 때 사용한다.