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

문제 링크

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

풀이 과정

다음은 처음에 생각하고 접근한 방법입니다.

function solution(numbers) {
		return numbers.map((num) => {
		    let tmp = num;
		
		    while (true) {
		        tmp++;
		        let cnt = 0;
		        let res = num ^ tmp;
		
		        while (res > 0) {
		            if ((res & 1) == 1) cnt++;
		            res >>= 1;
		        }
		
		        if (cnt >= 1 && cnt <= 2) break;
		    }
		
		    return tmp;
		});
}

위 코드는 다음과 같이 수행됩니다.

1. tmp라는 변수에 초기에 입력받은 숫자를 담고, 1씩 증가시키며 원본 값 num과 XOR 연산 을 실행합니다.
2. XOR 연산의 결과 1은 해당 비트가 다름을, 0은 해당 비트가 같음을 의미합니다. 따라서, 모든 비트 자리에 존재하는 1을 세어, 달라진 비트 개수를 구합니다.

10, 11번 테스트 케이스에서 시간초과가 발생해 아래와 같은 다른 풀이 방법이 필요했습니다.

아래 그림을 보며 설명하겠습니다.

x가 2일 땐, 비트 1개가 다른 3이 정답이 됩니다.

x가 7일 땐, 비트 2개가 다른 11이 정답이 됩니다.

x가 11일 땐, 비트 2개가 다른 13이 정답이 됩니다.

f(x)는 x에서 0이 위치하는 곳 과 관련이 있는 것을 알 수 있습니다.

• LSB에 0이 위치한다면, 해당 비트만 1로 토글시키면, 그 값이 비트 1개가 달라지는 최소값이 됩니다.
• LSB가 아닌 다른 곳에 0이 위치한다면, 해당 비트를 1로 토글시키고 오른쪽 비트를 0으로 토글시키면, 그 값이 비트 2개가 달라지는 최소값이 됩니다.

코드

function solution(numbers) {
    return numbers.map((num) => {
        let arr = num.toString(2).split("");
        let first = true;

        for (let i = arr.length - 1; i >= 0; i--) {
            if (arr[i] === "0") {
                if (i == arr.length - 1) {
                    arr[i] = "1";
                    return parseInt(arr.join(""), 2);
                } else {
                    arr[i] = "1";
                    arr[i + 1] = "0";
                    return parseInt(arr.join(""), 2);
                }
            }
        }

        arr.unshift("1");
        arr[1] = "0";
        return parseInt(arr.join(""), 2);
    });
}

console.log(solution([2, 7]));
console.log(solution([2, 3, 4, 5, 6]));