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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

양의 정수 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 함수를 완성해주세요.

2. 입력

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10¹⁵

3. 예제

numbers	result
[2,7]	[3,11]

4. 풀이

먼저 작은 수들의 변환되는 2진수 값과 해당 비트의 최소 비트 값을 확인해 보겠습니다.

 

2의 최소 비트 수를 확인 해보겠습니다.

10진수	2진수	최소 비트 2진수	최소 비트 10진수
2	10	11	3

 

3의 최소 비트 수를 확인해보겠습니다.

10진수	2진수	최소 비트 2진수	최소 비트 10진수
3	011	101	5

 

5의 최소 비트 수를 확인해보겠습니다.

10진수	2진수	최소 비트 2진수	최소 비트 10진수
5	101	110	6

 

7의 최소 비트 수를 확인해 보겠습니다.

10진수	2진수	최소 비트 2진수	최소 비트 10진수
7	0111	1011	11

 

붉은색으로 표시된 부분의 숫자들을 보면 2진수의 경우 오른쪽에서부터 1로 연속되어 있는 수는 1을 더할 경우 자릿 수가 추가되며 연속된 1의 개수 +1 개의 자리가 달라지게 됩니다.

 

3의 경우 오른쪽부터 연속된 1의 개수는 3번째 0을 만나기 전인 2개인 11입니다.

 

최소 수를 만들기 위해 1을 더한 2진 수는 100이 되고 그러면 과거 011과 100은 총 3개의 비트가 다른 수가 됩니다.

 

이번에는 2를 더한 2진 수는 101이 되고 그러면 과거 011과 101은 총 2개의 비트가 다른 수가 됩니다.

 

정답은 2를 더한 5가 됩니다.

 

이번에는 7을 확인해보도록 하겠습니다.

 

7의 경우 오른쪽부터 연속된 1의 개수는 4번째 0을 만나기 전인 3개인 111입니다.

 

최소 수를 만들기 위해 1을 더한 2진 수는 1000이 되고 그러면 과거 0111과 1000은 총 4개의 비트가 다른 수가 됩니다.

 

이번에는 2를 더한 2진 수는 1001이 되고 그러면 과거 0111과 1001은 총 3개의 비트가 다른 수가 됩니다.

 

이번에는 3을 더한 2진 수는 1010이 되고 그러면 과거 0111과 1010은 총 3개의 비트가 다른 수가 됩니다.

 

이번에는 4를 더한 2진 수는 1011이 되고 그러면 과거 0111과 1011은 총 2개의 비트가 다른 수가 됩니다.

 

정답은 4를 더한 11이 정답이 됩니다.

 

위 과정으로 알 수 있는 점화식은 오른쪽에서 왼쪽으로 최초 0을 만나기 까지의 연속된 1의 개수를 찾아

 

입력된 수 + 2^(연속된1의 개수 - 1)가 정답이 되는 것 입니다.

 

아래 표로 3과 7의 점화식을 풀어보았습니다.

10진수	2진수	연속된 1의 수	2^(연속된1의 수 -1)	정답
3	11	2	2	5
7	111	3	4	11

 

마지막으로 위 과정에서 빠지게 된 가장 오른쪽 비트가 0인 경우는 1만 더하면 기존의 비트는 모두 같은 상태에서 1개의 비트만 변하게 되는 것이므로 1만 더하면 정답이 됩니다.

 

5. 코드

전체 코드는 Git에 있습니다.

public long[] solution(long[] numbers) {
	long[] answer = new long[numbers.length];

	for (int i = 0; i < numbers.length; i++) {
		if(getRightToLeftBitOneCount(numbers[i]) == 0)
			answer[i] = numbers[i] + 1;
		else
			answer[i] = numbers[i] + (long)Math.pow(2, getRightToLeftBitOneCount(numbers[i]) - 1);
	}

	return answer;
}

public int getRightToLeftBitOneCount(long number){
	String bitString = Long.toBinaryString(number);

	int continuityOne = 0;
	for(int i = bitString.length()-1; i >-1; i--){
		if(bitString.charAt(i) == '1')
			continuityOne++;
		else
			break;
	}
    
	return continuityOne;
}