https://school.programmers.co.kr/learn/courses/30/lessons/77885
문제 설명
양의 정수 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 함수를 완성해주세요.
풀이
fun solution(numbers: LongArray): LongArray = numbers.map { number ->
if (number % 2L == 0L) {
number + 1
} else {
var nextHigherOneBit = number + 1
var rightOnesPattern = number xor nextHigherOneBit
rightOnesPattern = rightOnesPattern ushr 2
val result = nextHigherOneBit or rightOnesPattern
result
}
}.toLongArray()짝수인 경우 맨 끝 값이 무조건 0이 될테니 +1 만 더해주면 된다
문제는 홀수인 경우 였다.
홀수는 00001101, 00001111, 00010101 처럼 1로 끝나게 된다. 이들을 조건에 맞는 수로 변환하면
00001111, 00010111, 00010111 이 된다.
보면 맨끝에 있는 0을 1로 변환해주고 1로만 연속되어 있는 숫자의 경우 맨 왼쪽의 1을 앞으로 옮기고 원래 있던 자리엔 0을 넣어주면 된다.
이를 로직에서 어떻게 구현할까.
우선 n(number)은 마지막 비트가 무조건 '1'이다. 따라서 n + 1 을 하게 되면 연속된 1들은 0으로 바뀌고 그 다음 0이 1로 바뀔 것이다.
이를 이용해 가장 낮은 위치에 있는 0을 1로 변경해준다.
xor를 이용해서 number와 변경된 수의 차이점을 비트 패턴으로 저장한다.
예를 들어 7인 00000111은 +1 한 8 00001000과 차이가 나는 부분을 가져오면
00001111이 된다.
이는 숫자로 15를 나타내게 되는데,바뀐 숫자 부분 0111, 1111이 2칸 ushr를 이용해 여기서 2비트 만큼 오른쪽으로 논리 시프트를한다.
이제 처음에 +1한 nextHigherOneBit를 or 연산자를 통해 합쳐 주면 처음에 말한 규칙을 지키면서 로직 구현이 가능하다.
