프로그래머스 월간 코드 챌린지 시즌2 LV2 - 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

---

입출력 예

numbersresult

[2,7]

[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

---

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int idx=0;
        for(int i=0; i<numbers.length; i++){
                String as = Long.toBinaryString(numbers[i]);
                int cnt = -1;
                for(int j=as.length()-1; j>=0; j--){
                    if(as.charAt(j)=='0') break;
                    else {
                        cnt++;
                    }
                }
                answer[idx++] = numbers[i]+(getex(cnt));
        }
        return answer;
    }
   long getex(int num){
       long temp = 1;
       if(num<=0) return 1;
       for(int i=0; i<num; i++){
           temp*=2;
       }
       return temp;
   }
}

처음엔 XOR연산으로 1의 개수를 세는 방식으로 푸려고 시도했으나 시간 초과가 났다

0이전의 마지막 1의 자리에 1을 더해주면 2개의 비트가 차이 나게 되고, 그것이 최솟값이다.