프로그래머스 - 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의 모든 수 ≤ 10¹⁵

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

---

문제 풀이 방법

이 문제는 규칙을 찾으면 금방 해결 되는 문제이다.
자 그러면 규칙을 찾아보자.

위와 같이 10진수를 2진수로 바꿔 보자.
그러면 짝수인 경우에는 뒷자리가 0이고, 홀수인 경우에는 1인걸 볼 수 있다.

그러면 여기서 규칙이 하나 생성이 된다.
짝수인 경우 +1인한 값이 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 된다.

이제 홀수인 경우를 보자.
홀수인 경우에는 모든 숫자가 1로 이루어진 것과 1과 0으로 이루어진 경우 총 2개가 있다.

우선 1로만 이루어진 경우를 보자.
이때는 간단하게 앞 부분을 "10" 으로 변경만 하면 된다.

이번에는 1과 0으로 이루어진 홀수를 보자.
이때는 제일 뒤에 있는 0을 찾아서 0을 1로 변경하면 된다.

Long.toBinaryString(num)
Long.toString(num, 2)
...

10진수를 2진수로 변경하는 방법에 대해서는 다양한 방법이 있으며, 선택해서 사용하면 된다.

lastIndexOf()

IndexOf() 를 보통 많이 사용하였는데 마지막 인덱스를 찾는 lastIndexOf() 이건 처음 사용해보았다.

---

전체 코드

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];

            if(num % 2 == 0){
                answer[i] = num + 1;
            }
            else{
                String numTo2 = Long.toBinaryString(num);
                if(numTo2.contains("0")){
                    int idx = numTo2.lastIndexOf("0");
                    numTo2 = numTo2.substring(0, idx) + "10" + numTo2.substring(idx + 2);
                }
                else{
                    numTo2 = "10" + numTo2.substring(1);
                }
                answer[i] = Long.parseLong(numTo2, 2);
            }
        }
        return answer;
    }
}