프로그래머스 2개 이하로 다른 비트 자바 월간 코드 챌린지 시즌2

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

코딩테스트 연습 - 2개 이하로 다른 비트

 

안녕하세요 오랜만이네요 

오늘은 프로그래머스 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씩 더한다음 비트 차이가 2이하인 경우 배열에 저장하는 방식으로 구현했는대

이런식으로 구현하면 마지막 10,11번이 시간초과 가 뜹니다 

그래서 이런식으로 구현하면 안되고 

짝수인 경우에는 마지막 비트는 무조건 0 이기 때문에 그냥 1을 더한 값을 배열에 저장하면 되고(예를들어 2인경우 3이 우리가 원하는 값)

홀수 인 경우에는 살짝 복잡합니다 

만약 비트 중 0이 존재하는 경우 가장 마지막에 0을 1로 바꾸고 

바뀐 0 기준 가장 가까운 1을 0으로 바꿉니다 

 

만약 0이 존재하지 않는 경우 (ex 1111)

먼저 1을 더한 다음 

10000에서 10/000으로 나누어서

10다음 "1"을 붙이고 나머지 000을 1로 교체하면

10111 이 우리가 원하는 값입니다

 

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

        for(int i = 0 ; i<numbers.length ; i++){
          String binary =  Long.toBinaryString(numbers[i]);
                if(numbers[i]%2==0){
                    answer[i] = numbers[i]+1;
                }else{
                    int lastIndex = binary.lastIndexOf("0");
                    int firstIndex = binary.indexOf("1",lastIndex);

                    // 0이 없는경우
                    if(lastIndex==-1){
                        binary = Long.toBinaryString(numbers[i]+1);
                        binary = binary.substring(0,2)
                                +binary.substring(2,binary.length()).replace("0","1");

                    }else{
                        binary = binary.substring(0,lastIndex)
                                +"1"
                                +binary.substring(lastIndex+1,firstIndex)
                                +"0"
                                +binary.substring(firstIndex+1,binary.length());
                    }

                    answer[i]=Long.parseLong(binary,2);
                }

            }

        return answer;
    }

    public static void main(String [] args){
        Solution solution = new Solution();

        long [] data = solution.solution(new long[]{2,7});

        for(int i=0; i<data.length ; i++){
            System.out.println(data[i]);
        }
    }
}