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

📚 문제 설명

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

🔎 입출력 예

💻 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            // 1
            if(numbers[i] % 4 != 3) answer[i] = numbers[i] + 1;
            else { // 2
                String binary = Long.toBinaryString(numbers[i]);
                int idx = binary.lastIndexOf("0");
                // 2-1 
                if(idx != -1) {
                    String tmp = binary.substring(0,idx) + "10" + binary.substring(idx+2, binary.length());
                    answer[i] = Long.parseLong(tmp,2);
                } else { // 2-2. 모두 1로만 이루어질때
                    String tmp = "10" + binary.substring(1,binary.length());
                    answer[i] = Long.parseLong(tmp,2);
                }
                
            }
        }
        return answer;
    }
}

📖 Solution

1. 먼저 주어진 수를 4로 나누었을때 나머지가 3이 아니라면 1을 더한 값이 답이 된다.
2. 반면 나머지가 3이라면
   2-1. 비트 끝부터 탐색하여 0이 나오는 지점부터 10 비트를 넣어주면 된다. "01" -> "10"
   예) 0011 -> 0101
   2-2. 0이 없고 모두 1로만 이루어져있다면 최상위 비트를 하나 지우고 10 비트를 앞에 넣어주면 된다.
   예) 1111 -> 10111

• Long.parseLong(bit, 2)을 통해 비트를 다시 정수로 변환

이런 규칙을 어떻게 바로 찾아내는 걸까...