문제 설명
양의 정수 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
15
입출력 예
numbers | result |
[2,7] | [3,11] |
입출력 예 설명
입출력 예 #1
•
문제 예시와 같습니다.
나의 풀이
class Solution {
public long[] solution(long[] numbers) {
for (int i = 0; i < numbers.length; i++) {
int tail = Long.numberOfTrailingZeros(~numbers[i]);
if (tail <= 1) {
numbers[i]++;
} else {
numbers[i] += Math.pow(2, tail - 1);
}
}
return numbers;
}
}
Java
복사
Remark
•
처음에 단순 비트연산자 문제인줄 알고 풀었다가 시간초과가 떴는데, 쭉 늘어놓고 보니 패턴이 보였음
00000 +1
00001 +1
00010 +1
00011 +2 *
00100 +1
00101 +1
00110 +1
00111 +4 *
01000 +1
01001 +1
01010 +1
01011 +2 *
01100 +1
01101 +1
01110 +1
01111 +8 *
10000
10001
10010
10011
10100
10101
10110
10111
Java
복사
•
위의 패턴을 보면 01111과 같이 오른쪽으로부터 1이 4번 연속되는 수는 바로 다음 수인 10000과 비교했을 때 비트가 5개 만큼 다른 수가 됨
◦
10000 다섯 자리 중 최소 3개가 1로 바뀌어야 비트 차이가 2개 이하가 됨
◦
즉, 01111이 10111이 돼야하기 때문에, 01111이 10000이 되기 위한 1, 또 10111이 되기 위한 7, 총 (8)을 더해야 함
•
즉, 오른쪽으로부터 연속되는 1이 하나 더 늘어날 수록 올라가야 하는 수도 2배씩 늘어나는 것을 알 수 있음
•
풀이 아이디어
◦
맨 오른쪽으로부터 연속하는 1의 개수 구하기
▪
비트 반전(~) 후 Long.numberOfTrailingZeros로 개수를 구함
◦
개수가 1개 이하면 바로 다음 수가 정답
◦
2개 이상이면 기존 수 + 2 ^ ((맨 뒤의 연속되는 1의 개수) - 1)이 정답