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

문제 설명

양의 정수 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]

 

---

Solution.java

간단하게 풀 수 있을 법한 문제인 것 같은데 기존의 코드는 복잡해져서

좀 더 쉽게 풀 수 없을지 찾아보다 비트 연산자를 활용하여 더 간단하고 훨씬 빠르게 답을 찾을 수 있는 방법을 찾아 설명해보고자 합니다.

 

numbers 배열의 index : 1 번째 값 7을 예시로 설명

먼저 매개변수로 받는 배열을 복사합니다.

이 복사한 배열 answer은 매개변수로 받은 numbers 배열의 값과 비교하기 위해 사용됩니다.

long[] answer = number.clone();

 

numbers의 배열에 있는 값 7보다 커야하고 7과는 다른 비트를 비교해야하므로 복사한 배열 answer에 해당 위치 index : 1번째 값을 1 증감 시킵니다.

answer[1]++;

 

XOR 연산자를 이용해 두 수에서 같은 위치의 두 비트가 서로 다른 비트를 가졌다면 1로 아니라면 0인 비트를 반환 합니다.

7 이진법 : 0111
8 이진법 : 1000
----------------
XOR 연산 : 1111

answer[1] ^ numbers[1] = 1111

 

XOR연산으로 나온 비트의 값을 오른쪽 쉬프트 연산자를 이용해 맨 뒤의 2개의 비트를 제거 합니다.

15 (1111) >> 2 : 3 (0011)

 

이렇게 만들어진 비트를 answer[1]에 더하면 2개 이하로 다른 비트 중 제일 작은 수를 찾을 수 있습니다.

answer[1] += 3 (이진법 : 0011)
8 += 3 = 11 (1011)

 

표에서 숫자 7일 경우 7보다 크고 7과 비트가 2개 이하로 다른 수들 중에서 제일 작은 수는 11입니다.

11(1011)은 이 구해지는 과정을 보면 

8(1000)에 XOR연산자(^)와 오른쪽 쉬프트 연산자(>> 2)를 이용해 구한 값 15(11)을 더하면 1011이 된다는 규칙을 알 수 있습니다.

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

 

 

만약 3개 이하로 다른 비트를 구한다면 >> 3, 5개 이하로 다른 비트를 구한다면 >> 5

이런식으로 XOR연산자와 오른쪽 쉬프트 연산자를 이용해 n개 이하로 다른 비트를 구할 수 있습니다.

 

정답 코드

import java.util.Arrays;

public class 다른비트 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new long[]{2, 7})));
    }

    public static long[] solution(long[] numbers) {
        long[] answer = numbers.clone();
        for (int i = 0; i < numbers.length; i++) {
            answer[i]++; // x보다 큰수로 만든다.
            answer[i] += (answer[i] ^ numbers[i]) >> 2;
        }
        return answer;
    }
}