[프로그래머스] 2개 이하로 다른 비트 (Lv 2) - javascript

📝 문제

양의 정수 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
   

🤔 나의 풀이

function solution(numbers) { 

    let answer = [];

    for(let i = 0; i < numbers.length; i++) {

        let n = numbers[i].toString(2);
        let zero = n.match(/0/) || [];

        if(zero.length) {
            let arr = n.split('');
            for(let j = n.length-1; j >= 0; j--) {
                if(arr[j] === '0') {
                    arr[j] = '1';
                    if(arr[j+1]) arr[j+1] = '0';
                    break;
                }
            }
            answer.push(parseInt(arr.join(''), 2));
        }

        else {
            let arr = new Array(n.length + 1).fill(1);
            arr[1] = 0;
            answer.push(parseInt(arr.join(''), 2));
        }
    }

    return answer;
}

 
테스트 케이스 1,2,4번을 통과하지 못해서 한참을 헤맸다.

n이 0일 경우를 고려하지 못해서, 수정하고 통과했다.

for문을 두 번이나 돌기 때문에 속도가 느리다.
 

풀이 과정

1. 이진수에 0이 있나 없나 확인
   1-1. 있으면 뒤에서부터 0 찾기 -> 찾으면 1로 바꿈
   (맨 뒷자리가 0이면 그것만 바꿈 / 아니라면 뒷자리까지 10으로 바꿈)
2. 없으면 길이 n.length + 1 에 모두 1인 이진수 만들기 -> 두번째 숫자 0으로 바꿈
    

• 정확도 테스트 결과

  

  
   

🔑 다른 풀이

푸는 원리는 다들 비슷하지만, 비트를 변경하기 위해 분류하는 기준과 과정이 다르다.
 

1. 01을 찾아 변경하는 풀이

function solution(numbers) {

    let answer = [];

    for(let i = 0; i < numbers.length; i++) {

        let n = '0' + numbers[i].toString(2);

        if(n[n.length-1] === '0') n = n.slice(1,-1) + '1';

        else {
            for(let j = n.length; j >= 0; j--) {
                if(n[j] === '0') {
                    n = n.slice(0,j) + '10' + n.slice(j+2);
                    break;
                }
            }
        }
        answer.push(parseInt(n,2));
    }

    return answer;
}

 
일단 비트의 모든 수가 1이라면 맨 앞에 숫자를 붙여서 변경해야 하므로 맨 앞에 0을 붙이고 시작한다.
 

1. 맨 뒤 비트가 0일 때
   단순히 맨 뒤 비트를 1로 바꾸면 된다

2. 맨 뒤 비트가 0이 아닐 때
   비트 중 '01'을 찾아서 '10'으로 변경해준다.
    

• 정확도 테스트 결과

  

  
   

2. 짝수, 홀수 구분해서 처리하는 풀이

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

    function check(n) {
        if(!(n%2)) return n+1;

        n = '0' + n.toString(2);
        let idx = n.lastIndexOf('0');
        n = n.slice(0,idx) + '10' + n.slice(idx+2);
        return parseInt(n,2);
    }

    numbers.forEach(n => answer.push(check(n)));
    return answer;
}

 
이진수의 맨 끝자리가 0 이면 짝수임을 이용한 풀이

구분을 위해 따로 순회를 돌 필요가 없어서 간단하고 빠르다.
 

• 정확도 테스트 결과

  

  
   

---

참고

gobae.tistory
dev-note-97.tistory