월간 코드 챌린지 시즌2 > 2개 이하로 다른 비트

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

처음에는

 

주어진 숫자(numbers[i])에 +1(이하 B)을 하고

 

XOR 연산을 한 후

 

Long.bitCount 를 통해 1의 갯수의 차이를 구한다.

 

이 차이가 2이하일 경우 answer[i]에 값을 저장한다.

 

아닐 시 B에 +1을 한다.

 

위를 반복했다.

 

결과적으로 시간 초과가 발생했다.

 

아무래도 숫자가 커질 수록 (주어진 범위가 10의 15승이다)

 

비트 1개의 차이를 찾는게 오래 걸리는 것이라고 판단했다.

 

그래서 단순하게 생각했다.

 

그냥 2진법을 생각하면

 

맨 오른쪽부터 1, 2, 4, 8, 16, ........ 2의 n배 수를 나타낸다.

 

그러면 그 숫자들을 더한다.

 

더해서 나온 수와 numbers[i] 값을 XOR 연산 후

 

1의 개수를 세어본다.

 

그게 2 이하면 정답이라는 것이다.

 

7을 이진법으로 바꿨을때의 길이만큼 1부터 2의 배수를 더한다.

 

나온 값과 비교값을 XOR 연산 후 1의 갯수를 세어서 1의 갯수 차이를 확인

 

 

코드

 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        long a = 0, plus = 1;
        long tmp = 0;
        for(int i = 0; i <numbers.length; i++){
            a = numbers[i];
            plus = 1;
            String num = Long.toBinaryString(a);
            for(int j = 0; j < num.length(); j++){
                tmp = Long.bitCount(a ^ (a + plus));
                if(tmp <= 2) {
                    answer[i] = a + plus;
                    break;
                }
                plus *= 2;
            }
        }
        return answer;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요