[프로그래머스(Programmers)][자바(java)] (Lv2) 2개 이하로 다른 비트 <월간 코드 챌린지 시즌2>

 

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

 

class Solution {
	public long[] solution(long[] numbers) {
		int n = numbers.length, m, i, j, k = 0; String s;
		long ans[] = new long[n], num;
		for( i = 0; i < n; ++i ) {
			num = numbers[i];
			s = Long.toBinaryString( num );
			m = k = s.length();
			for( j = m-1; j >= 0; --j ) {
				if( s.charAt(j) == '0' ) {
					k = m-j-1;
					break;
				}
			}
			num += Math.pow( 2, k == 0 ? k : k-1 );
			ans[i] = num;
		}
		return ans;
	}
}

 

n  =>  n보다 크고 n과 비트가 1~2개 다른 수 들 중에서 제일 작은 수
n이 짝수  =>  n+1
n이 홀수  =>  n을 2진수로 변환하고 2^0( = 1 )의 자리에서부터 볼 때 가장 처음 나오는 0을 1로 고치고
                   그 앞의 1을 0으로 고친 수

*  num  :  10진수
*  s  :  num을 2진수로 변환한 문자열
*  m  :  s의 길이
*  k  :  s에서 1의 자리부터 탐색했을 때 가장 처음 나오는 0의 자릿수

ex)  num = 7, s = “111”, m = k = 3

j	0 1 2
m-j-1	3 2 1 0
	0 1 1 1	( 4 + 2 + 1 )
->	1 0 1 1	( 7 + 8-4 = 7 + (2^3-2^2) = 7 + 2^(3-1) =7 + 4 )