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

문제

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

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

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

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

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

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

풀이

최솟값을 구하는 방법이 무엇일까 고민했었다.
순차적으로 1씩 증가하는 방법과 1, 2자리 무작위 변경하는 방법중 순차 증가가 최솟값을 구하는데 더 효율적이라 판단했었다.
다음과 같은 순서를 따랐다.

1. 1 증가
2. XOR비교
3. 1갯수 세기
4. 조건에 만족하면 arr에 추가, 아니면 1로

import java.lang.*;
import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        List<Long> list = new ArrayList<>();

        for(long i : numbers) {
            int count = 1;
            while(true) {
                if (check(i, i + count)) {
                    list.add(i + count);
                    break;
                }
                count++;
            }
        }

        return list.stream().mapToLong(i -> Long.valueOf(i)).toArray();
    }

    static boolean check(long first, long second) {

        long num = first ^ second;
        String str = Long.toBinaryString(num);
        str = str.replaceAll("0", "");
        if (str.length() > 2) {
            return false;
        }
        return true;
    }
}

XOR비교는 서로 다른 비트를 검사할 때 쓰인다.
다른비트에 XOR연산을 하면 1이 되기 때문이다.(보안수업때 배웠던 것을 여기서 쓸줄이야...)
그러나 마지막 2개 테스트에서 시간초과가 났다.
더 효율적인 것을 찾아야 했다.

케이스를 짝 수 일때와 홀 수 일때 두가지로 나누었다.
짝수 일 때는 1을 더한 수가 조건에 맞는 가장 작은 수 이다.
홀수 일때는 두가지로 나뉜다. 모두 1로 이루어질때와 1과0이 모두 포함되었을때 이다.

모두 1로 이루어 질 때는 자릿수가 증가하는게 필연적이다. 만일 111이면 1_ _ _ _ 가 되는데
최소로 만드려면 0이 최대한으로 앞으로 위치해야 한다. 따라서 10111이 되는 것 처럼 앞에 10을 붙힌다.

혼합 되었을 때는 가장 작은 자릿수에서 부터 처음 발견한 0을 10으로 치환한다.

이 규칙대로 구성하면 효율적으로 풀이 할 수 있다.

import java.lang.*;
import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int j = 0;
        for(long i : numbers) {
            if (i % 2 == 0) {
                answer[j++] = i + 1;
            } else {
                StringBuilder sb = new StringBuilder(Long.toBinaryString(i));
                if (!sb.toString().contains("0")) {
                    sb.replace(0, 1, "10");
                } else {
                    int index = sb.lastIndexOf("0");
                    sb.replace(index, index + 2, "10");
                }
                answer[j++] = Long.parseLong(sb.toString(), 2);
            }
        }

        return answer;
    }
}

https://github.com/Win-9/Algorism/blob/main/programers/2%EA%B0%9C%20%EC%9D%B4%ED%95%98%EB%A1%9C%20%EB%8B%A4%EB%A5%B8%20%EB%B9%84%ED%8A%B8/README.md