[Java] 2개 이하로 다른 비트

프로그래머스

 

문제 풀이

비트를 다루는데 생소하다면 연습해볼 좋은 문제이다. 문제의 조건이 비트를 다룰줄 알아야만 이해할 수 있는 조건이기 때문이다.

문제의 조건은 x에 대해서 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수이다.

 

숫자를 2진수로 변환해본다면 짝수는 무조건 뒷자리가 0이다. 따라서 1만 더해준다면 짝수는 조건에 해당하는 수를 금방 찾을 수 있다.

문제는 홀수이다. 홀수일때 조건을 만족하는 수들의 규칙을 찾는것이 어려웠다. x = 15라고 예시로 들어보겠다. 15를 2진수로 변환하면 01111 이다. x보다는 커야 한다고 했으므로 01110은 조건을 충족하는 숫자가 아니다. 그러므로 앞쪽의 비트를 바꿔줘야한다. 

01111 -> 10111 이라면 비트가 1~2개 다른 수이면서 x보다 크다. 

 

이를 구현하기 위해서는 연속된 1의 개수를 세야한다. 1의 개수를 cnt라고 해보자. 01111은 cnt가 4이다. 이제 01111에서 10111이 되기위해서는 얼마를 더해야할까? 01111에서 1000을 더한다면 10111이 될 것이다. cnt를 구한 이유가 여기서 나온다. 01111에 더해준 1000은 2^3 = 2^(cnt-1)이다. 즉 x가 홀수 일때 조건에 만족하는 수는 x + 2^(cnt-1)이다. 다른 수에 대해서도 계산을 해보면 조건을 충족한다.

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        // 짝수인 경우 -> num + 1;
        // 홀수인 경우 -> num + 2 ^ ((1의 개수) - 1);
        
        for (int i = 0; i < numbers.length; i++) {
            // 짝수
            if (numbers[i] % 2 == 0) {
                answer[i] = numbers[i] + 1;
            } 
            // 홀수
            else {
                long tmp = numbers[i];
                long bit = 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++) {
                    bit *= 2;
                }
                
                answer[i] = numbers[i] + bit;
            }
        }
        
        return answer;
    }
}