프로그래머스 코딩테스트 문제 - [Lv.2] 2개 이하로 다른 비트 (Java)

📌 문제

문제 출처 - 링크

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

  수	비트	다른 비트의 개수
  2	000...0010
  3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

  수	비트	다른 비트의 개수
  7	000...0111
  8	000...1000	4
  9	000...1001	3
  10	000...1010	3
  11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

입출력 예

numbers	result
[2,7]	[3,11]

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

알고리즘 분류

• 구현
• 비트 연산

📋 문제 요약 설명

• 주어진 양의 정수 x에 대하여 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하라.

---

💡 알고리즘 설계 / 접근 방법

1. x가 짝수인 경우는 비트가 1개 다른 수가 제일 작은 수다.

   • 짝수이기 때문에 비트로 표현해도 마지막 비트는 0이다.

   • x에 1을 더해주면 비트에서도 마지막 비트만 1이 되므로 가장 작은 수가 된다.

2. x가 홀수인 경우는 비트가 2개 다른 수가 제일 작은 수다.

   • x와 x+1를 XOR 연산을 하고,

     • XOR 연산은 두 비트의 각 자릿수를 비교해서 다른 비트만 1로 표시된다.

     • XOR 연산을 통해서 두 수의 바뀐 비트 위치를 알아낼 수 있다.

   • 오른쪽 시프트 연산을 2개 한다.

     • 시프트 연산을 통해 바뀐 비트 개수를 줄이는 작업을 하는 것이다.

     • 오른쪽으로 2칸 쉬프트하면, 상위 비트만 유지되면서 바뀌는 비트 개수가 줄어든다.

   • 위에 계산한 것을 x에 더하고, 1도 더해준다.

     • 1을 더해주는 이유는 비트가 바뀌는 지점을 정확히 한 칸 더 이동하기 위한 것이다.

     • +1을 하지 않으면 결과가 x 이상이지만, 조건인 "2개 이하의 비트만 다른 x보다 큰 수 중 가장 작은 수" 를 만족하지 못할 수 있다.

---

✅ 풀이

시간 복잡도 → O(N)

1. for 문 : O(N)
2. 짝수일 때 : O(1)
3. 홀수일 때 : 모든 연산이 O(1)

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

        for (int i = 0; i < numbers.length; i++) {
            long n = numbers[i];
            
            // 짝수 : 마지막 비트만 0 → 1로 바뀌면 됨
            if (n % 2 == 0) { 
                answer[i] = n + 1;
            } 
            // 홀수 : 다른 비트 수가 2개 이하인 수를 만들어야 함
            else {
                // XOR 연산(^) 후 오른쪽 시프트 연산한 걸 더하면 2개 이하로 다른 비트를 구할 수 있다.
                long xor = n ^ (n + 1); 
                answer[i] = n + (xor >> 2) + 1;
            }
        }

        return answer;
    }
}