[코딩 테스트] javaScript #33

문제

문제 설명
양의 정수 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]

[출처] 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/77885)

---

답

function solution(numbers) {
    let answer = [];
    numbers.forEach((el)=> {
        let nextNum = el
        let bit = 3
        while(bit>2) {
            nextNum ++
            let binaryNextNum = nextNum.toString(2);
            let binaryTargetNum = el.toString(2).padStart(binaryNextNum.length, '0')
            let count = 0;
            for(let i=0; i<binaryTargetNum.length; i++){
                if(binaryNextNum[i]!==binaryTargetNum[i]){
                    count ++
                    if(count===3) break;
                }
            }
            bit = count
        }
        answer.push(nextNum)
    })
    return answer
}

처음에는 고민없이 문제에 나온 로직대로 숫자를 더하면서 확인하는 방식으로 답을 작성했으나 역시 테스트 2개가 실행 시간 초과로 실패하였다. f(x)의 규칙성을 찾아내서 더 효율적인 방법으로 풀어야하는 문제였다.

f(x)로 도출되는 값을 보니 일정한 규칙에 의해 값이 도출되는 것을 알 수 있었다.

1. 이진법으로 변환된 값의 마지막 숫자가 0이라면 기존 숫자에 1을 더한 값이 출력된다.
   ex) 입력값이 10이라면 이진법으로 변환 시, 1010이고 1을 더한 값인 11은 이진법으로 변환 시 1011이 되기 때문에 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수라는 조건을 만족한다.

2. 이진법으로 변환된 값의 마지막 숫자가 0이 아니라면, 뒷자리에 가까운 01을 10으로 변환한 값이 출력된다.
   ex) 입력값이 11이라면 이진법으로 변환 시, 1011이고 이 값보다 큰 수 중에서 작은 수를 찾기 위해서는 중간의 0을 1로 바꿔줘야 하는데 2개까지 다른 수도 허용되기 때문에 그다음 자리의 1을 0으로 바꿔주어서 더 작은 값을 도출할 수 있다.

function solution(numbers) {
    const answer = [];
    numbers.forEach((el)=>{
        let targetNum = '0' + el.toString(2)
        if(targetNum[targetNum.length-1] === '0'){
            answer.push(el+1)
        } else {
            for(let i=targetNum.length-2; i>=0; i--){
                if(targetNum[i] === '0'){
                    answer.push(parseInt(targetNum.slice(0,i) + '10' + targetNum.slice(i+2,targetNum.length),2))
                    break;
                }
            }
        }
    })
    return answer
}

이진법으로 변환한 숫자가 1111처럼 모두 1인 경우때문에 맨앞에 0을 추가한 후에 위 규칙대로 값을 도출하였다. 로직은 간단하지만 규칙성을 찾아내지 못하면 풀기 어려운 문제라고 생각한다.