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

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

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

 

풀이

이문제는 홀수와 짝수를 나눠서 풀이하였습니다.

 

짝수의 경우엔 2진수로 표현할 때 마지막 자리수가 항상 0 이므로 이를 1로만 바꿔주면 됩니다. 즉, +1만 해주면 간단히 구해집니다.

 

홀수의 경우 2진수로 표현할 때 마지막 자리수 부터 1이 연속으로 등장하는 횟수(cnt)를 세줍니다. 그런 뒤 01 을 10으로 바꾸는 연산을 해줘야합니다.

이 때 이를 10진수의 연산으로 간단하게 구하는 식은 ans = num + 2^(cnt-1)입니다. (이유는 위의 그림 참고!)

 

class Solution {
    public long[] solution(long[] numbers) {
        int len = numbers.length;
        long[] answer = new long[len];
        for(int i=0; i<len; i++){
            //짝수
            //ans = num + 1
            if(numbers[i] % 2 == 0){
                answer[i] = numbers[i] + 1;
            }
            //홀수
            //ans = num + 2^(cnt)
            else{
                long tmp = numbers[i];
                long cal=1;
                int cnt=0;
                //1이 몇개 연속되는지 찾기
                while(tmp>0){
                    if(tmp % 2 == 1)
                        cnt++;
                    else
                        break;
                    tmp /= 2;
                }
                for(int j=0; j<cnt-1; j++){
                    cal*=2;
                }
                answer[i] = numbers[i] + cal;
            }
        }
        return answer;
    }
}