P77885. 2개 이하로 다른 비트

문제

제출 코드

• 사용 알고리즘 : 비트마스킹

문제를 읽자마자 비트마스킹 문제인걸 알았지만, 비트연산자는 자주 안썼다보니 조금 헤멨다.

주어진 숫자의 홀짝여부에 따라 제일 작은 수를 찾는 방법이 달라진다.

1. 주어진 숫자가 짝수일 경우

   짝수는 비트로 숫자를 바꾸면 무조건 마지막 자리수가 0이므로, 그냥 1을 더한 값이 조건을 만족하는 가장 작은 숫자가 된다.

2. 주어진 숫자가 홀수일 경우

   뒷자리에서부터 0인 숫자를 탐색해서, 가장 뒤에 있는 0을 1로 바꾸고 그 뒷자리에 있던 1을 0으로 바꿔준다.

   자리수별로 0인지 1인지 탐색을 어떻게 해야할지 고민하는 부분에서 시간이 걸렸다.

   각 자리수에 해당되는 숫자 (1, 2, 4, 8, …)와 비교할 숫자를 &연산을 하면, 해당 자리수가 0일 경우엔 0이 나오는 점을 이용하여 구분했다.

비트마스킹은 생소하다 보니 확실히 헷갈린다. 많이 풀어봐야겠다.

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        int N = numbers.length;
        long[] answer = new long[N];

        for(int i=0; i<N; i++){
            if(numbers[i]%2==0) {
                answer[i] = numbers[i]+1;
            }else{
                long bit=1;
                while((numbers[i] & bit) > 0){
                    bit *= 2;
                }
                answer[i] = numbers[i] + bit/2; //(+ bit - bit/2)
            }
        }

        return answer;
    }
}