2개 이하로 다른 비트 (LV2)

문제 설명

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

---

입출력 예numbersresult

[2,7]

[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

풀이

이 문제는 어떤 수학적? 규칙을 찾아야 하는 문제이다.

그래서 일단 가장 단순한 방식으로(다른비트수가 2개이하가 될때까지 1씩 증가) 1부터 100까지 돌려보았다.(숫자가 조금만 높아도 처리시간이 굉장히 오래걸릴 것이다.)

내가 찾은 규칙은, 주어진숫자의 맨 뒷자리부터 연속된 1의갯수를 N 이라 할때, 주어진숫자에 2의(N-1)승을 더해주는것이다. 설명이 애매한거 같으니 아래 예제를 보자.

num = 31; // 주어진 숫자 str = "11111"; // num 을 2진수로 변환 n = 5; // str의 뒤에서부터 연속된 1의갯수 result = num + 2^(n-1); 정답 : 47 (2진수: 101111)

num = 47; // 주어진 숫자 str = "101111"; // num 을 2진수로 변환 n = 4; // str의 뒤에서부터 연속된 1의갯수 result = num + 2^(n-1); 정답 : 55 (2진수 : 110111)

썩 좋은 방법은 아닌거 같지만 일단 이 규칙을 사용해서 로직을 짜 보았다.

public long[] solution(long[] numbers) {
    long[] answer = new long[numbers.length];
    
    for (int i = 0; i < numbers.length; i++) {
    	long curr = numbers[i];
    	String binStr = String.format("%50s", Long.toBinaryString(curr));
    	
    	int lastOneCnt = 0; // 뒤에서부터 연속된 1의 갯수 세기
    	for (int j = 49; j >= 0; j--) {
    		if (binStr.charAt(j) == '1') lastOneCnt++;
    		else break;
    	}
    	if (lastOneCnt == 0) {
    		answer[i] = curr + 1;
    	} else {
    		answer[i] = (long) (curr + Math.pow(2, lastOneCnt-1));
    	}
    }
    return answer;
}

통과는 했지만 뭔가 찜찜하다. 좀더 세련된 방법이 있을것 같은데 나중에 더 고민해 봐야겠다.