프로그래머스_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

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

[문제 분석]

완전 탐색으로 수를 1씩 증가시켜가며 비트 수를 비교하였더니 시간초과가 났다.

그래서 경우의 수를 나눠 비트를 변환시켜 해결하였다.

 

1. numbers[i]가 짝수인 경우, 이를 2진수로 변환했을 때는 항상 마지막 비트가 0이다. 따라서 마지막 비트를 1로 바꿔주고 answer[i]에 넣어준다.

 

2. numbers[i]가 2^k-1인 경우, 모든 비트가 1이다. 예를 들어 numbers[i] = 7 이고, 이를 2진수로 변환하면 111이다. 이러한 경우에는 맨앞에 1을 추가해주고 가장 첫 비트를 0으로 변경시킨다. 111 -> 1011

 

3. 그 외의 경우 가장 뒤에 등장하는 0을 1로 변경시켜주고 그 이후에 가장 먼저 등장하는 1을 0으로 변경시켜준다. "01"을 찾아 "10"으로 변경시켜주면 된다. (ex) 101 -> 110   1001 -> 1010    101111 -> 110111  101011-> 101101)

 

 

[시간 초과 코드 - 완전 탐색]

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int d_count=0;
        
        for(int i=0;i<numbers.length;i++){
            d_count=0;
            String s1 = Long.toBinaryString(numbers[i]);
            Long temp = numbers[i]+1;
            
            while(true){
                d_count=0;
                String s2 = Long.toBinaryString(temp);
                if(s1.length()!=s2.length()){
                    for(int j=0;j<s2.length()-s1.length();j++)
                        s1 = "0"+s1;
                }
                for(int j=0;j<s1.length();j++){
                    if(s1.charAt(j)!=s2.charAt(j)){
                        d_count++;
                    }
                }
                if(d_count<=2){
                    answer[i]=temp;
                    break;
                }
                else
                    temp+=1;
            }
        }
        return answer;
    }
}

 

[최종 코드]

import java.lang.*;
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int d_count=0;
        
        for(int i=0;i<numbers.length;i++){
           if(numbers[i]%2==0)  //짝수인 경우
               answer[i]=numbers[i]+1;
            
            else{
                
                if(Long.bitCount(numbers[i])==(Long.toBinaryString(numbers[i])).length())  //2^k-1 -> 모든 비트가 1
                {
                    String s = "10"+Long.toBinaryString(numbers[i]).substring(1);
                    answer[i]=Long.parseLong(s,2);
                    
                }
       
                else{
                    int t=0;
                    String s=Long.toBinaryString(numbers[i]);
                    
                    for(int j=s.length()-2;j>=0;j--){
                    
                        if(s.substring(j,j+2).equals("01")){
                            if(j<s.length()-2)
                                s = s.substring(0,j)+"10"+s.substring(j+2);
                            else
                                 s = s.substring(0,j)+"10";
                            answer[i]=Long.parseLong(s,2);
                            break;
                        }
                            
                        
                    }
                    
                }
                
                    
            }
        }
        return answer;
    }
}