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

https://programmers.co.kr/learn/courses/30/lessons/77885#

코딩테스트 연습 - 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]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

---

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

        for(int i = 0; i < numbers.length; i++){
            long num = numbers[i];
            long num2 = num >> 2;
            
            num2 = num2 << 2;
            num2 = num2 | 3;
            
            if(num2 == num){
                answer[i] = num + 1;
                answer[i] = answer[i] | num;
                
                long temp = ~((answer[i] - num) / 2);
                
                answer[i] = answer[i] & temp;
                
            }else{
                answer[i] = num+1;
            }
            

        }
        
        return answer;
    }
}

핵심 코드, 푸는법:

비트연산 문제이다.

2진수에서 맨뒤에 두자리가 11로 시작하면 연산이필요하다.

그외에는 1만더해주면 된다.

 

ex)

이진법으로 변환한 수가 101010110001111 일때

여기서 봐야할 부분은 맨뒤의 1이 연속해서 나오는 부분이다.

101010110001111 

우선 답은 101010110010111 인데

원래 값에서 이 값을 구하기위해서는 비트연산을 해주면된다.

 

우선 연속으로 1이 2번이상 나오는지 확인하기 위해 Shift연산을 사용하여 확인한다.

101010110001111 >> 2 -> 1010101100011

1010101100011 << 2 -> 101010110001100

 

101010110001100 | 11 -> 101010110001111 

연산하기 전 값과 같으므로 1이 2번이상 나온다.

 

이후 답을 구해준다.

 

원래값 + 1

101010110001111  +  1  -> 101010110010000

 

원래값 | 계산된값

101010110001111 | 101010110010000

-> 101010110011111

 

이제 101010110011111 빨간 부분을 0으로 만들어주면 된다. 

이를 위해서는 우선 계산된 값에서 기존값을 빼주고 not을 붙인다.

 

계산된 값 - 원래값

101010110011111 - 101010110001111 -> 000000000010000

 

~계산된값

-> 111111111101111

 

그다음 이전에 구했던 101010110011111 값과 & 연산을 한다.

101010110011111 & 111111111101111 -> 101010110010111