[KOTLIN] 2개 이하로 다른 비트

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

코딩테스트 연습 - 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의 모든 수 ≤ 1015

입출력 예

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

풀이

1. 문제를 그대로 for 문을 이용하여 검색할 경우 테스트 케이스 10, 11에서 시간 초과가 발생한다.

2. 문제를 수학적으로 접근해서 규칙성을 찾아야 시간 초과가 발생하지 않는다.

3. 짝수의 경우에는 그 수에 1을 더하면 결과가 된다.

4. 홀수의 경우 두 가지 경우로 나누어 진다.

4-1. 홀수 중 숫자 7 처럼 2진수로 비트 변환 시 0이 없는 경우에는 첫번째와 두번째 수사이에 '0' 을 넣는다.

4-2. 홀수 중 숫자 9 처럼 2진수로 비트 변환 시 0이 있는 경우에는 마지막 0을 찾아 '0' 과 그 뒤의 '1' 의 자리를 바꾼다.

전체 코드

class Solution {
    fun solution(numbers: LongArray): LongArray {
        var answer = LongArray(numbers.size)

        numbers.forEachIndexed { index, number ->
            // number 가 짝수인지 홀수 있지 확인 한다.
            var result = number.toString(2)
            // 1. 짝수일 경우
            result = if (number % 2 == 0L) {
                result.substring(0, result.length - 1) + "1"
                // 2. 홀수일 경우
            } else {
                // 0이 포함되어 있지 않은 홀수
                if (!result.contains("0")) {
                    "10" + result.substring(1, result.length)
                } else {
                    val lastZero = result.lastIndexOf('0')
                    result.substring(0, lastZero) + "10" + result.substring(lastZero + 2, result.length)
                }
            }

            answer[index] = result.toLong(2)
        }

        return answer
    }
}