[코딩테스트] 프로그래머스 javascript 2단계 - 2개 이하로 다른 비트

2개 이하로 다른 비트

- 이 문제는 규칙을 찾는 문제이다.

- 짝수는 2진수로 전환시 마지막 자리가 0이다. 그러니 1을 더한 값을 리턴하면 된다.

- 홀수는 가장 빨리 0이 나온 자리를 1로 만들고 나머지는 0으로 더하고 이것을 1자리 낮춰서 빼면 된다.

홀수 일때,

101 => 101(원본) + 10(0을 1로 뒷자리를 0으로) + 1(앞 수에서 1자리 제거) = 110

1001 => 1001 + 10 - 1 = 1010

 

 

 

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

양의 정수 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 함수를 완성해주세요.

 

 

 

문제 풀이

이 문제는 구현력, 수학적 능력을 중요하게 생각하는 문제였다.

- 이 문제를 처음에 while 문으로 하나씩 확인했다. 

- 길이가 다르면 잘라내고 다른 길이 만큼 더해준 뒤 진행했다.

- 하지만 이렇게 하면 테스트 10번과 11번이 시간초과로 실패하게 된다.

function solution(numbers) {
    var answer = [];
    while (numbers.length){
        const cur = numbers.shift();
        let str = cur.toString(2)
        let n = cur + 1;
        while(true){
            let count = 0
            let arr = n.toString(2);
            if (str.length<arr.length){
                let len = arr.length-str.length
                if(count>2) continue;
                count += len
                arr = arr.slice(len)
            }if (str.length>arr.length){
                let len = str.length-arr.length
                count += len
                if(count>2) continue;
                str = str.slice(len)
            }
            for (let i=0;i<Math.max(str.length,arr.length);i++){
                if (str[i]!==arr[i]) count++
                if(count>=3) break;
                // console.log('count  :'+count)
            }
            if (count===1 ||count===2){
                answer.push(n); break;
            } else {
                n++
            }
            
        }
     
    }
    return answer;
}

 

비트연산을 생각해보자.

비트 연산시에 1과 0 두개만을 사용하고,

비트 연산의 차이를 1~2개만을 인정한다고 했다.

즉, 짝수의 경우는 마지막 자리가 0일테니 +1 만 해주면 된다.

홀수의 경우는 뒤에서 부터 0이 등장한 자리를 +1하고 뒷자리를 0으로 만들어준다.

홀수 일때,

101 => 101(원본) + 10(0을 1로 뒷자리를 0으로) + 1(앞 수에서 1자리 제거) = 110

1001 => 1001 + 10 - 1 = 1010

즉!

뒤에서부터 01을 찾고 이를 10으로 바꾸자

만약 '0'이 없는 경우를 대비해 앞에 0을 붙이자.

function solution(numbers) {
    let answer = [];
    while(numbers.length){
        const cur = numbers.shift()
        if (cur%2===0) { // 짝수
                let sum = cur+1;
                answer.push(sum);     }
        else {
            let arr = '0'+cur.toString(2)
            // console.log(arr)
            const index = arr.lastIndexOf('01')
            // console.log(index)
            arr = arr.slice(0,index)+ '10' + arr.slice(index+2)
            // console.log(arr)
            answer.push(parseInt(arr,2))
        }
    }
    return answer;
}