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

학습 키워드: 

 

77885 - 2개 이하로 다른 비트

1) 문제 설명 (원문은 링크 참고):

프로그래머스

 요약: 배열 numbers에 주어진 숫자들을 2진수로 변환했을때, 변환된 수보다 크면서 동시에 비트가 1~2개 다른 가장 가까운 수를 찾는 함수 f(n)을 작성한 뒤, numbers 모든 수에 대해 f(n)을 실행한 결과를 담은 배열을 반환하는 문제다. 예를 들어, 7을 2진수로 변환하면 0111이고, 7보다 크면서 비트가 1~2개 다른 가장 가까운수는 1011으로 11이 된다.

 조건: 1 <= numbers.length <= 100,000, 0 <= numbers[i] <= 10^(15)

 

 

2) 첫 시도 및 패턴 파악:

 처음에 문제를 쭉 읽어보면서 주어진 숫자를 2진수로 변환하고, 비트 변환을 수행하면서 조건에 맞는 수를 찾고, 해당 수를 다시 10진수로 변환하여 반환할 배열에 차례대로 넣어준다는 있는 그대로의 flow를 따라서 코드를 작성하려 헀는데, StringBuilder도 쓰고 숫자도 바꾸고 이것저것 하다보니 뭔가 풀이가 지저분해진다고 느껴져서 문제를 다시 읽으면서 패턴을 파악해보기로 했다.

 

 먼저 문제의 첫 번째 조건은 자신보다 큰 수를 찾는 것이기 때문에 어떤 숫자를 찾든 1을 우선 더해줘야 한다. 그런데 만약 현재 숫자의 마지막 비트가 0이라면, 1을 더하는 즉시 비트수가 1개 차이나는 숫자를 만들 수 있기 때문에 끝 비트가 0인 숫자(=짝수)의 경우 현재 숫자 +1의 값이 f(n)의 결과 값이 된다.

 

 다음 케이스는 현재 숫자의 끝 자리 비트가 1인 경우다. 이 경우는 그 다음 자리의 비트가 0인지 1인지에 따라 결과가 바뀌는데, 먼저 비트가 01로 끝나는 수의 경우는 마찬가지로 1을 더했을 때 10으로 바뀌면서 정확히 끝의 두 자리 비트가 01 과 10으로 2개 비트의 차이가 생기게 된다. 따라서 01로 끝나는 수 또한 해당 수 +1의 값이 f(n)의 결과 값이 된다.

 

 마지막 경우는 끝 자리에 1이 반복되어 나타나는 경우가 되는데, 이 경우가 바로 예시에서 주어진 7 처럼 0111 같은 모양을 띄는 경우다. 이 숫자에 1을 더하게 되면 1000 이 되어 끝 부분의 모든 1이 0으로 바뀌고, 첫 번째로 만나는 0을 1로 바꿔주게 된다. 이 작업이 수행되면 원래의 숫자와는 정확히 1의 개수(3) + 1 만큼의 비트 자리가 차이나게 되는데, 여기서 비트의 차이를 2개 까지 줄일 수 있는 가장 작은 큰 수를 구한다는 것은 결국 변환되어 0이 된 뒷 자리 비트들을 끝에서부터 차례대로 1로 바꿔서 비트의 차이를 2개 까지 줄이는 것을 말한다. 따라서 2진수 0111의 경우 1을 더한 1000에서 맨 뒤의 2개 비트를 1로 바꿔 차이를 2개로 만든 수는 1011, 즉 10진수의 11이 된다. 이를 그대로 코드로 표현하면 다음과 같다.

 

 

3) 패턴 파악 후 array만 이용한 풀이:

import java.lang.Math;

class Solution {
    public long[] solution(long[] numbers) {
        long[] ret = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            ret[i] = findNearest(numbers[i]);
        }
        return ret;
    }
    
    private long findNearest (long number) {
        long ret = number + 1;
        if (number % 2 == 0) return ret;
        int count = 0;
        while (number % 2 != 0) {
            count++;
            number /= 2;
        }
        if (count-- == 1) return ret;
        for (int i = 0; i < count; i++) {
            ret += Math.pow(2, i);
        }
        return ret;
    }
}

 

4) 리팩토링:

 findNearest의 마지막 부분의 불필요한 loop를 제거하기 위해 코드를 리팩토링 해보았다.

import java.lang.Math;

class Solution {
    public long[] solution(long[] numbers) {
        long[] ret = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            ret[i] = findNearest(numbers[i]);
        }
        return ret;
    }
    
    private long findNearest (long number) {
        if (number % 2 == 0) return number + 1;
        int count = 0;
        long temp = number;
        while (temp % 2 != 0) {
            count++;
            temp /= 2;
        }
        if (count == 1) return number + 1;
        return number + (long) Math.pow(2, count - 1);
    }
}