[프로그래머스] 2개 이하로 다른 비트

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

---

첫번째 시도 -> 실패

class Solution {
    public long[] solution(long[] numbers) {
        int len = numbers.length;
        long[] answer = new long[len];
        for(int i=0; i<len; i++) {
            answer[i] = getBigChgBit(numbers[i]);
        }
        return answer;
    }

    public long getBigChgBit(long num) {
        if(num % 2 == 0) return num+1;
        
        String binary = Long.toBinaryString(num);
        long result = num+1;
        
        while(true) {
            if(getDifferentCnt(Long.toBinaryString(num), Long.toBinaryString(result++)) < 3) {
                break;
            }
        }
        return result -1;
    }
    
    public int getDifferentCnt(String s1, String s2) {
        if(s1.length() > s2.length()) {
            s2 = "0"+s2;
        } else if(s1.length() < s2.length()) {
            s1 = "0"+s1;
        }
        
        int cnt = 0;
        for(int i=s1.length()-1;i>=0;i--) {
            if(s1.charAt(i) != s2.charAt(i)) cnt++;
        }
        return cnt;
    }
}

 

10, 11에서 time out이 났다.

입력받은 num에서 하나씩 카운트하며 비트를 하나하나 비교해서 시간이 너무 오래 걸렸던 것 같다.

while(true)라는 반복문도 자칫하면 무한루프에 빠질까 굉장히 신경쓰인다....ㅠㅠ

 

 

두번째 시도 -> 성공

class Solution {
    public long[] solution(long[] numbers) {
        int len = numbers.length;
        long[] answer = new long[len];
        for(int i=0; i<len; i++) {
            answer[i] = getBigChgBit(numbers[i]);
        }
        return answer;
    }

    public long getBigChgBit(long num) {
        if(num % 2 == 0 || num == 1) return num+1;
        
        String binary = Long.toBinaryString(num);
        StringBuilder sb = new StringBuilder(binary);
        
        if(sb.indexOf("0") < 0) {
            sb.insert(0,'0');
        }
        
        for(int i=binary.length()-1;i>=0;i--) {
            if(sb.charAt(i) == '0') {
                sb.setCharAt(i, '1');
                if(i!=binary.length()-1) {
                    sb.setCharAt(i+1, '0');
                }
                break;
            }
        }
        return Long.valueOf(sb.toString(), 2);
    }
    
}

• 짝수인 경우에는 +1만 해주면 됨 (마지막 비트가 무조건 0이니까)
• 가장 끝자리부터 0인 것을 찾아 1로 변경
  만약 오른쪽 숫자가 1이라면 0으로 변경 (비트 수는 최대 2개까지 달라도 되니까)

 

 

---

다른 사람 풀이

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;
    }
}

 

answer[i]에 (answer[i]^numbers[i])>>>2 하는 이유를 모르겠다...

혹시 나중에 누군가 검색해서 이 포스팅을 보신다면 이유를 말씀해주시기를 ㅜ.ㅜ

 

^ 는 XOR 연산

>>> 는 java에만 있는 연산자로 오른쪽으로 주어진 수만큼 이동하고 왼쪽은 0으로 채운다.

ex: (1001 >>> 1) == 0100