Programmers - 2개 이하로 다른 비트 with JAVA (V)

 

문제

십진수가 주어지고 해당 수보다 큰 수 중에서 2진수로 변환했을 때, 해당 수와 해당 수보다 큰 수의 비트 차이가 2개 이하인 수들 중 가장 작은 수를 구하라.

 

 

 

 

로직

이 문제는 3가지를 고려해주면 된다.

1. 해당 수가 4로 나눴을 때 3이 아닌가? 

-> 이런 경우는 1을 더해주면 문제 조건에 맞는 수를 찾을 수 있다.

2. 모두 1인가?

-> 예를 들어, 11111 이 있다고 가정하자.

-> 해당 수에 1을 더하면 100000이 될 것이다. 

-> 이 때, 가장 앞자리 10은 고정하고 나머지를 맞추는게 가장 최소이면서 2개 이하 차이나는 수이다. 101111

-> 로직 : 0을 포함하는지 확인 - 10을 앞자리로 설정 - 나머지는 길이에 맞추어 1로 채움

3. 모두 1은 아닌가?

-> 예를 들어, 100111과 같은 경우를 의미한다.

-> 예시들을 통해 알 수 있듯이 111과 같이 연속된 1이 있다면 바로 다음수가 가장 작으면서 차이가 2개이하인 수가 해당 수에 1을 더한 값이 아니게 된다.

-> 이러한 경우에는 10(10)11 으로 변경하면 된다. 즉, 원리는 괄호안에 부분만 다르고 모든 부분이 같게 설정하면 가장 작으면서 차이가 2개이하인 수를 찾을 수 있다.

-> 로직 : 0을 포함 안하는지 확인 - 0의 마지막 인덱스를 구한다. - 그 인덱스를 기준으로 앞은 그대로 하고 10 추가 나머지 추가 순으로 한다.

 

 

 

 

 

코드

import java.util.*;
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i=0; i<numbers.length; i++){
            long number = numbers[i];
            if(number % 4 != 3){
                answer[i] = number+1;                
            }
            else{
                String value = Long.toBinaryString(number);
                String new_value = "";
                if(!value.contains("0")){
                    new_value += "1" + "0";
                    new_value += value.substring(1);
                }
                else{
                    int x = value.lastIndexOf("0");
                    new_value += value.substring(0, x) + "10";
                    new_value += value.substring(x+2);
                }       
                answer[i] = Long.parseLong(new_value, 2);
            }
        }
        return answer;
    }
}