[프로그래머스] 2개 이하로 다른 비트(77885)

1. 문제 풀이 아이디어

• 짝수일 때는 1을 더하고, 홀수일 때는 가장 뒤에 있는 0을 찾아 10으로 바꾸면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] % 2 == 0) {
                answer[i] = numbers[i] + 1;
                continue;
            }
            String b = Long.toString(numbers[i], 2);
            String result = null;
            boolean chk = false;
            for (int j = b.length() - 1; j >= 0; j--) {
                if (b.charAt(j) == '0') {
                    result = b.substring(0, j) + "10" + b.substring(j + 2);
                    chk = true;
                    break;
                }
            }
            if (!chk) {
                result = "10" + b.substring(1);
            }
            answer[i] = Long.parseLong(result, 2);
        }
        return answer;
    }
}

3. 정리

• numbers[i]가 짝수라면 1을 더해 answer[i]에 저장한 후, 다음 반복으로 넘어간다.

• 홀수일 경우, 해당 숫자를 이진수 문자열로 변환하고, 변환 여부를 확인하는 chk 변수를 사용한다.

• 이진수 문자열의 맨 끝에서부터 반복문을 돌며 0을 찾으면, 이를 10으로 바꾸고 chk를 true로 설정한 후 반복문을 종료한다.

• chk가 false라면, 문자열의 맨 앞부분을 10으로 바꾼다.

• 변환된 이진수 문자열을 다시 long 타입으로 변환해 answer[i]에 저장한다.

4. 더 좋은 코드 리뷰

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = numbers.clone();
        for(int i = 0; i< answer.length; i++){
            answer[i]++;
            answer[i] += (answer[i]^numbers[i])>>>2;
        }
        return answer;
    }
}

• answer[i]++
• 먼저 1을 더해서 가장 오른쪽 비트(LSB)를 처리한다.

• (answer[i] ^ numbers[i]) >>> 2
• XOR 연산으로 두 숫자의 비트 차이를 확인하고,
• 2칸 오른쪽으로 시프트해 추가로 보정해야 할 비트를 찾는다.

• answer[i] += ...
• 보정값을 answer[i]에 더해 최종 결과를 만든다.

• 비트 연산을 활용해 연산량을 최소화하고 효율적으로 동작한다.

• 비트 연산 연습을 충분히 해야 도출할 수 있을 것 같다.