[프로그래머스][LEVEL2] 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씩 증감하면서 비트가 다른 갯수를 비교하는 방식으로는 시간초과가 되는 문제이다. 규칙성을 찾아야 할 필요가 있는데 짝수의 경우 바로 다음수가 1비트 다르면서도 입력 받은 number 보다 큰 수가 되고 홀수의 경우 가장 낮은 자릿수의 0과 1의 위치를 바꿔주면 조건에 부합하는 숫자가 된다는 규칙을 파악하는게 핵심이다. 비트에 얼마나 익숙한가에 따라서 문제 난이도가 달라지는 것으로 보인다.

 

# 솔루션 플로우

1. 입력 받은 numbers를 모두 순회한다.

2. 현재 num이 2로 나누었을때 나머지가 0 이면 짝수이므로 num + 1를 얻는다.

3. 현재 num이 홀수 일 경우 num을 2진 비트로 치환하고 가장 뒤의 0의 위치를 찾는다.(4,5)

4. 0이 없을 경우 가장앞의 1을 제거하고 10을 삽입해준다.

5. 0과 바로 뒤의 1을 서로 바꿔준다.

6. 얻어진 2진문자열을 10진 숫자로 형변환해준다.

7 모든 순회가 끝난후 얻은 result를 반환한다.

1. FP

function solution(numbers) {
    return numbers.map((num) => {
        if (num % 2 === 0) return num + 1;
        const pivot = Array.from(num.toString(2));
        const bdx = pivot.lastIndexOf('0');
        if (bdx === -1) {
            pivot.shift();
            pivot.unshift('10');
        } else {
            pivot[bdx] = 1;
            pivot[bdx + 1] = 0;
        }
        return parseInt(pivot.join(''), 2);
    });
}