[프로그래머스][JAVA] 2개 이하로 다른 비트 (비트마스크?)

(틀린 코드)

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        
        for(int i=0; i<numbers.length; i++){
            long currNum = numbers[i];
            long targetNum = numbers[i]+1;
            
            while(true){
                Long xor = currNum^targetNum;
                int diffBitNum = 0;
                while(xor>0 && diffBitNum<=2){
                    diffBitNum = (xor%2==1)? diffBitNum+1 : diffBitNum;
                    xor/=2;                                    
                }
                if(diffBitNum<=2){
                    answer[i] = targetNum;
                    break;
                }
                targetNum++;
            }
        }
        return answer;
    }
}

 

 

자꾸 테케10~11 시간초과남

 

 

 

문제에서 주어진 예제를 살펴보니 규칙을 찾을 수 있었음

일단 문제에서 주어진 number를 binary로 바꿔준 후에

값이 0인 가장 작은 자릿수를 찾아야함

그리고 그 자리수를 1로 바꿔주고

그 뒤에 있는 자리수를 0으로 바꿔주면 됨

(가장작은 자릿수의 0을 찾았기 때문에 그 뒷자리는 반드시 1이 오므로)

ex) 1011101010...... 011 -> 1011101010...... 101 (이게 문제에서 요구하는 최소값)

 

 

근데 0이 가장 끝부분인 경우가 있음

문제에서 주어진 예제 10 -> 11 (뒤에 자릿수가 없기 때문에 이거는 비트를 1개만 바꾸는 것이 최소값임)

 

그리고 0이 없는 경우인

11111111.........11111111로만 가득찬 경우

가장 앞자리를 0으로 바꾼 후에 다시 가장 앞자리에 1을 붙여주면됨

 

11111111.........11111111(n자리수) -> 101111111.........11111111(n+1자리수)

 

xor만들어서 for문으로 왼손으로 비비고 오른손으로 비비고 

2로나누고비비고할필요 없이

 

가장 작은 자리수의 0을 찾기만하면 시간초과 해결함

 

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            String currNumStr = Long.toBinaryString(numbers[i]);
            int len = currNumStr.length();
            Long answerNum = 0L;
            
            int zeroIdx = -1;
            for(int j=len-1; j>=0; j--){
                if(currNumStr.charAt(j)=='0'){
                    zeroIdx = j;
                    break;
                }
            }
            
            if(zeroIdx == len-1){
                answerNum = Long.parseLong(currNumStr, 2)+1;
            }
            else if(zeroIdx == -1){
                StringBuilder sb = new StringBuilder();
                sb.append("1");
                sb.append(currNumStr);
                sb.setCharAt(1,'0');
                answerNum = Long.parseLong(sb.toString(), 2);
            }
            else{
                StringBuilder sb = new StringBuilder(currNumStr);
                sb.setCharAt(zeroIdx,'1');
                sb.setCharAt(zeroIdx+1,'0');
                answerNum = Long.parseLong(sb.toString(), 2);
            }
            answer[i] = answerNum;
 
            
        }
        
        return answer;
    }
}

 

 

 

 

더 잘짠코드.. 이걸로하니까 시간 50배는 더빠름

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = numbers.clone();
        for(int i = 0; i< answer.length; i++){
            answer[i]++;
            answer[i] += (answer[i]^numbers[i])>>>2;
        }
        return answer;
    }
}