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

문제 설명

 

프로그래머스

 

접근 방법

처음 이 문제에 접근했었던 방식은 주어지는 숫자(number)와 해당 숫자에 1씩 더한 숫자(number + 1)를 XOR 연산(다른 비트일 경우 1)해준 다음 이를 이진수 형태로 바꿔주어 1의 개수를 세주도록 했습니다.

 

        for (long number : numbers) {
            long target = number;
            while (true) {
                String xor = Long.toBinaryString(number ^ ++target);

                long count = xor.chars().filter(ch -> ch == '1').count();

                if (count > 0 && count < 3) {
                    result.add(target);
                    break;
                }
            }
        }

 

하지만 주어지는 numbers의 길이는 10만일뿐만 아니라 numbers 요소 자체들이 최대 10의 15승이라는 수로 이러한 작업을 일일이 해주어선 제한 시간 내에 모든 연산을 다 할 수 없었습니다.

 

그리하여 결국 해당 문제는 나름의 규칙성(수학?)을 찾는 작업을 통해 해결할 수 있었습니다.

 

우선 number가 0 ~ 11인 경우를 고려해보겠습니다. 이 값들을 이진수로 나타낼 때 LSB 부근에 뭔가 규칙성이 보입니다.

 

 

바로 4개의 숫자씩 끝자리가 00, 01, 10, 11로 끝난다는 점입니다.

 

이때 00으로 끝나는 수에 1을 더한다면 LSB 한자리의 비트만 다르고 나머지 비트는 동일할 것입니다.

 

마찬가지로 10로 끝나는 수에 1을 더한다면 LSB 한자리의 비트만 다르고 나머지 비트는 동일할 것입니다.

 

또한 01로 끝나는 수에도 1을 더한다면 LSB 및 LSB 왼쪽 비트 총 두자리의 비트만 다르고 나머지 비트는 동일할 것입니다.

 

문제에서는 자리수가 1~2개만 다르면 되므로 주어진 수보다 크면서 가장 작은 수인 number + 1의 값이 00, 10, 01로 끝나는 수들에 대해선 정답이 되게 됩니다. 이때 이진수 형태 상 00, 01, 10으로 끝나는 십진수들은 4를 나누었을 때 나머지가 3을 제외한 0, 1, 2가 되는 수들입니다. 따라서 아래와 같이 결과값을 산출할 수 있게 됩니다.

 

        long[] result = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] % 4 != 3) {
                result[i] = numbers[i] + 1;
            }
            
            // ...

 

하지만 11로 끝나는 수들은 뭔가 애매합니다. 11(십진수 3)에다가 1을 더하면 100이 되버려 3자리의 비트가 다르게 됩니다. 그리하여 이에 대해선 따로 규칙성을 찾기로 했습니다. (이러한 규칙성을 찾는데에는 처음 일일이 XOR 연산 작업해주었던 방법으로 작성했던 로직을 이용하면 도움이 됩니다.)

 

(왼쪽) 이진수가 11로 끝나는 수 (오른쪽) 해당 수의 정답이 되는 수

 

이때 이진수가 11로 끝나는 수와 해당 수의 정답이 되는 수의 차이에는 뭔가 규칙성이 있어 보입니다. 우선 3, 11, 19, 27, ... 등 3에서 시작해 8씩 커지는 수들은 정답이 되는 수와 2 만큼의 차이가 나는 것을 볼 수 있습니다. 또한 7, 23, 39, ... 등 7에서 시작해 16씩 커지는 수들은 정답이 되는 수와 4 만큼의 차이가 나는 것을 볼 수 있습니다. 이후론 15에서 시작해 32씩 커지는 수들은 정답이 되는 수와 8 만큼의 차이가 나고있습니다.

 

처음 규칙성을 띄우는 3, 11, 19, 27, ... 등의 수열은 8씩 커지므로 8로 나누었을 때 나머지 값이 항상 3입니다. 이는 2의 2승에서 1을 뺀 값에 해당됩니다. 이후 7, 23, 39, ... 등의 수열은 16씩 커지므로 16으로 나누었을 때 나머지 값이 항상 7로 이는 2의 3승에서 1을 뺀 값에 해당됩니다.

 

이러한 규칙성을 반영했을 때 주어지는 수(number)에 대해 다음과 로직을 작성할 수 있게 됩니다.

 

            long multiple = 8;
            long exponent = 2;
            long v = (long) Math.pow(2, exponent) - 1;
            long add = 2;

            while (number % multiple != v) {
                add *= 2;
                multiple *= 2;
                v = (long) Math.pow(2, ++exponent) - 1;
            }

            return number + add;

 

이로써 최종적인 규칙성을 구해낼 수 있었습니다. 하지만 프로그래머스에서 다른 사람들의 풀이를 보니 시프트 연산자만으로도 간단하게 정답을 도출하는 등 이보다 더욱 효율적인 방법들이 많이 있었습니다. 😅 본 풀이는 저만의 풀이 방식이오니 참고만해주시면 되겠습니다. 👀

 

나의 소스 코드

class Solution {

    public long[] solution(long[] numbers) {
        long[] result = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] % 4 != 3) {
                result[i] = numbers[i] + 1;
            } else {
                long multiple = 8;
                long exponent = 2;
                long v = (long) Math.pow(2, exponent) - 1;
                long add = 2;

                while (numbers[i] % multiple != v) {
                    add *= 2;
                    multiple *= 2;
                    v = (long) Math.pow(2, ++exponent) - 1;
                }

                result[i] = numbers[i] + add;
            }
        }

        return result;
    }
}

 

참고자료

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