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

코딩테스트 연습 - 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의 모든 수 ≤ 10¹⁵

풀이

To-Do 리스트

1. 기존 수에 1씩 더함.
2. 기존 수와 1를 더한 수를 xor연산, 그 수를 이진법으로 표현
3. 1의 갯수를 세서 2보다 커지면 break.
4. 반복완료 후 2보다 작거나 같은 수인 경우 break.
5. 해당 되지 않는 경우 1를 더함.
6. 반복하여 나온 값을 저장.

결과

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        // x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
        
        int k = 0;
        for(long num : numbers){
            long ins = num+1L;
            
            while(true){
                int cnt = 0;
                String str = Long.toBinaryString(num ^ ins);
                char[] crr = str.toCharArray();
                for(char c : crr){
                    if(c == '1') cnt++;
                    if(cnt > 2) break;
                }
                if(cnt <= 2) break;
                ins += 1L;
            }
            answer[k++] = ins;
        }
        return answer;
    }
}

알게 된 점

💥 테스트 10, 11번 시간초과
💥 규칙을 찾아서 실행.

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        // x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
        
        int k = 0;
        for(long num : numbers){
            String str = Long.toBinaryString(num);
            char[] crr = str.toCharArray();
                
            int cnt = 0;           
            for(int i = crr.length-1; i >= 0; i--){
                char c = crr[i];
                if(c == '0') {
                    break;
                }
                cnt++;
            }
            answer[k++] = num+Math.round(Math.pow(2,cnt-1));

        }
        return answer;
    }
}