[77885번] 2개 이하로 다른 비트

월간 코드 챌린지 시즌 2

 

✔️ 문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

✔️ 제한 사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10^15

 

✔️ 입출력 예

 

✔️ 코드 구상

numbers의 숫자와 그 이후 숫자를 순서대로 XOR 연산한 후 나온 2진값에서 1의 갯수가 2개 이하인 숫자를 찾는다.

 

✔️ 1차 코드(실패)

• 테스트 케이스 10, 11번은 숫자 하나하나 비교해서는 절대 풀 수 없을거 같다..

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];

        for(int i = 0; i < answer.length; i++) {
            answer[i] = result(numbers[i], numbers[i] + 1);
        }

        return answer;
    }

    public long result(long ogNum, long incNum) {
        while(true) {
            String comp = Long.toBinaryString(ogNum ^ incNum++);

            long count = comp.chars().filter(c -> c == '1').count();

            if(count <= 2) {
                return incNum - 1;
            }
        }
    }
}

 

✔️ 2차 코드(성공)

• 도저히 모르겠어서 '질문하기'에서 힌트를 얻어서 해결했다.
• 오른쪽에서부터 가장 처음 '0' 을 '1'로 바꾸고 그 위치에서 오른쪽을 '0'으로 바꾸면 조건에 맞는 숫자를 찾을 수 있다.
• '0'이 없는 수는 가장 왼쪽을 '0'이라고 판단한다.

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];

        for(int i = 0; i < answer.length; i++) {
            answer[i] = result(numbers[i], numbers[i] + 1);
        }

        return answer;
    }

    public long result(long ogNum, long incNum) {
        StringBuilder sb = new StringBuilder("0" + Long.toString(ogNum, 2));
        int index = sb.length() - 1;

        while(index >= 0) {
            if(sb.charAt(index) == '0') {
                sb.setCharAt(index, '1');
                break;
            }
            index--;
        }

        if(index < sb.length() - 1) {
            sb.setCharAt(index + 1, '0');
        }

        return Long.parseLong(sb.toString(), 2);
    }
}

 

📄 원문

프로그래머스