2개 이하로 다른 비트 (자바, Java)

 

조건 자체가 어렵지는 않았다. 단, 규칙성을 찾아야해서 수학문제에 가까웠다.

처음에는 규칙성을 찾을 수 없어서, 완전탐색으로 구현하였다.

범위를 보고, 이중반복문이 들어가면 안될거라는걸 직감했는데, 예상대로였다.

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i=0; i<answer.length; i++) {
            long n = numbers[i]+1;
            while (true) {
                int count = 0;
                String str1 = Long.toBinaryString(numbers[i]);
                String str2 = Long.toBinaryString(n);
                int l1 = str1.length();
                int l2 = str2.length();
                int len = l2-l1;
                
                if (l1!=l2) {
                    StringBuilder sb = new StringBuilder();
                    for (int j=0; j<len; j++) {
                        sb.append('0');
                    }
                    str1 = sb.toString() + str1;
                }
                
                for (int k=0; k<l2; k++) {
                    if (str1.charAt(k)!=str2.charAt(k)) count++;
                    if (count>2) break;
                }
                
                if (count>2) n++;
                else {
                    answer[i] = n;
                    break;
                }
            }
        }
        return answer;
    }
}

 

두개의 테스트케이스가 시간초과.

조금 더 생각하다가, 할 수 없이 풀이를 보았다.

조금 더 대입법을 생각해볼걸 그랬나, 싶긴 했다. 최소한, 짝수는 규칙성을 찾을 수 있었다. 뭔가 부끄러웠다.

홀수의 규칙성은 조금 어려웠다. 내가 참조한 풀이에서는, 1만 있는경우, 0을 포함한 경우를 나누어 생각했다.

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i=0; i<numbers.length; i++) {
            if (numbers[i]%2==0 || numbers[i]<=1) {
                answer[i] = numbers[i]+1;
                continue;
            } else {
                String bit = Long.toBinaryString(numbers[i]);
                int l = bit.length();
                if (!bit.contains("0")) {
                    answer[i] = Long.parseLong("10"+Long.toBinaryString(numbers[i]>>1), 2);
                } else {
                    StringBuilder sb = new StringBuilder(bit).reverse();
                    int idx = sb.indexOf("0");
                    sb.setCharAt(idx, '1');
                    sb.setCharAt(idx-1, '0');
                    answer[i] = Long.parseLong(sb.reverse().toString(), 2);
                }
            }
        }
        return answer;
    }
}

 

 

그리고 프로그래머스 내에서 다른사람이 푼 풀이를 보았다.

 

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

 

???

 

 

??????

미쳤다. 말도 안되는 효율을 보여주었다.

코드의 길이와 가독성, 실행효율 모두 압도적이다. 메모리 사용이 아주약간 높기는 했다.

왜 이게 정답일까? 그걸 잘 모르겠다.

한번 곱씹어보는데,

 

처음에 1을 더한다. 최솟값은 +1값이기떄문.

원본값과 1을 더한값의 xor을 비교한다. 2개 이하꺼잔 달라도 되서 허용범위, 따라서 비트를 오른쪽으로 2칸 이동시킨다.

해당 숫자를 더해준다. profit!

 

일단 내 해석결과긴한데...조금 더 엄밀하게 알고싶다.

 

=> 콜라 문제를 물어본 수학과 친구에게 물어보았습니다.

참고로 이 친구는 코딩을 잘 몰라서...문법을 제가 설명하면서 물어보았습니다.

 

문제풀이의 원리

x가 주어질때, f(x)를 구하는 문제라 하면,

x를 비트(2진수)로 변환 후, 뒤에서부터 최초로 0이 나오는 부분을 찾는다.

 

=> 이것이 코딩에서 x xor (x+1)을 하면, 맨 앞자릿수가 되는 1이 된다.

이진법에서 +1을 했을때,

1이 있는 부분은 0으로 바뀌면서, 앞자릿수가 +1이 된다.

0이 있는 부분은 1로 바뀌고, 이후 앞자릿수에 영향을 주지 않는다.

따라서, 바뀌어야 하는 수의 범위를 정할 수 있게 된다.

 

이후, 2개 이하는 허용범위, 달라도 되기 때문에,

>>2로 비트를 오른쪽으로 2칸 밀어 과감히 생략해주는 방식이다.

 

비슷한 문제가 나왔을때, 이걸 떠올리기도 힘들고, 떠올려도 살떨려서 쉽게 할 수 있을것 같진 않으나...

재미있는 문제였고, 호기심이 해결되어 만족스럽다.