[java] 프로그래머스 - 2개 이하로 다른 비트 (Level 2)

코딩테스트 연습 - 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 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10¹⁵

🖨 입출력 예

numbers	result
[2,7]	[3,11]

📂 분류

구현

💡 풀이

처음에는 정수들을 이진수로 바꾼 뒤 하나씩 비교해서 비트가 다른 수가 2개 이하이라면 answer에 저장하는 방식으로 풀었다. 하지만 테스트 케이스 10, 11에서 시간 초과가 떴다. 제한 사항을 보니 왜 시간 초과가 떴는지 이해가 갔다.

이 문제를 풀기 위해선 규칙을 찾아야했다.

손으로 직접 f(n) = x를 구해본 결과 짝수의 규칙은 정말 쉽게 나왔는데 그 규칙은 f(n) = n + 1 다.
홀수는 규칙을 찾기가 생각보다 어려웠다. 홀수의 규칙은 이렇다.

• 최하위 비트부터 탐색해서 "01"을 찾는다.
• "01" 있을 경우
  • "01"을 "10"으로 바꿔준다.
• "01" 없을 경우
  • 최상위 비트를 하나 지워주고 맨 앞에 "10"을 삽입한다.

예시)
n = 3인 경우
toBinaryString(n)을 한다면 "11"이 된다.
"01"이 없기 때문에 상위비트를 지워주고 그 자리에 "10"을 넣어면 "101"이 된다.
따라서 f(3) = 5가 된다.

n = 11인 경우
toBinaryString(n)을 한다면 "1011"이 된다.
"01"이 존재하기 때문에 "01"을 "10"으로 바꿔주면 "1101"이 나온다.
따라서 f(11) = 13이 된다.

💻 코드

• 처음 시도(10, 11 시간 초과)

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = {};
        answer = new long[numbers.length];
        int idx = 0;
        for (long n : numbers) {
            for (long i = n + 1;; i += 1) {
                if (getNumberOfDiffrentNumbers(Long.toBinaryString(n), Long.toBinaryString(i)) <= 2) {
                    answer[idx] = i;
                    break;
                }
            }
        }
        return answer;
    }

    private static int getNumberOfDiffrentNumbers(String origin, String comparison) {
        int count = 0;
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) != comparison.charAt(i)) {
                count += 1;
            }
        }
        return count;
    }
}

• 정답 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = {};
        answer = new long[numbers.length];
        int idx = 0;
        for (long n : numbers) {
            if (n % 2 == 0) {
                answer[idx] = n + 1;
            } else {
                StringBuilder binary = new StringBuilder(Long.toBinaryString(n));
                int len = binary.length();
                if (binary.toString().contains("01")) {
                    for (int i = len; i > 0; i--) {
                        if (binary.substring(i - 2, i).equals("01")) {
                            binary.setCharAt(i - 1, '0');
                            binary.setCharAt(i - 2, '1');
                            break;
                        }
                    }
                } else {
                    binary.deleteCharAt(0);
                    binary.insert(0, "10");
                }
                answer[idx] = Long.valueOf(binary.toString(), 2);
            }
            idx += 1;
        }
        return answer;
    }
}