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

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

프로그래머스

---

문제

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

입출력 예

---

풀이

참고로 저는 비트 시프트 연산자를 잘 사용하지 못해서 비트 연산자를 사용하지 않는 방법으로 풀었습니다..! 

제가 생각했을 때 베스트 풀이 방법은 아닌 듯해서 이런 풀이 방법도 있구나 하고 참고용으로만 봐주시면 좋을 것 같습니다.

 

구해야 할 것은 "x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수" 인데 이 수에는 규칙이 있습니다.

(고수님 덕분에 팁을 알게 되었습니다.)

 

x를 2진수로 변환했을 때, 뒤에서부터 가장 먼저 나오는 0을 1로 바꾸고 그 0의 오른쪽에 있는 1을 0으로 바꾸면 됩니다.

x보다 큰 수여야 하니까 0을 1로 변환해야하고, 비트가 1~2개 다르면서 그 중 제일 작은 수여야 하니까 바로 오른쪽에 있는 1을 0으로 바꿔주는 것입니다.

여러 1이 있겠지만 여러 개를 0으로 바꿔주면 비트가 3개 이상 달라지게 되기 때문에 1개만 바꿔줍니다. 또 그 중 제일 작아야 하기 때문에 가장 높은 자리인 0의 오른쪽 자리의 1을 0으로 바꿔줍니다. 만약 더 오른쪽에 있는 1을 바꿔준다면 그 수는 제일 작은 수가 아니니까요! 

 

이 규칙은 조건이 있는데 0이 하나 이상 포함돼야 하고, 뒤에서 가장 먼저 나오는 0의 오른쪽에 1이 하나라도 있어야 합니다.

그래서 3가지의 조건을 나눠서 코드를 작성했습니다.

1. 0으로 끝나는 수일 때 => 0을 1로 바꿔줍니다.
   • ex) 110(6) -> 111(7)
2. 0이 중간에 포함되어 있을 때 => 뒤에서부터 가장 먼저 나오는 0을 1로 바꾸고 오른쪽에 있는 1을 0으로 바꿉니다.
   • ex) 1001(9) -> 1010(10)
3. 중간에 0이 포함되어 있지 않고 1로만 이루어져 있을 때 => 첫번째 1을 0으로 바꾸고 앞에 1을 붙여줍니다.
   • ex) 1111(15) -> 10111(23)

 

이렇게 구하고자 하는 수를 구하고 10진수로 변환해주면 됩니다.

---

소스코드

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];
            String biNumber = Long.toBinaryString(number);
            String biFNum = "";
            
            boolean noZero = true;
            for(int j=biNumber.length() - 1; j>=0; j--){
                if(biNumber.charAt(j) == '0'){
                    noZero = false;
                    
                    // 0으로 끝날 때
                    if(j == biNumber.length() - 1){
                        biFNum = biNumber.substring(0, j) + "1";
                    }
                    
                    // 중간에 0이 있을 때
                    else{
                        biFNum = biNumber.substring(0, j) + "10" + biNumber.substring(j+2, biNumber.length());
                    }
                    break;
                }
            }
            
            // 1만 있을 때
            if(noZero){
                biFNum = "10" + biNumber.substring(1, biNumber.length());
            }
           
            long fNum = Long.parseLong(biFNum, 2);
            answer[i] = fNum;

        }
        

        return answer;
    }
}