문제 설명
양의 정수 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
문제 접근 방법 - 1
- 입력 배열의 크기에 맞춰 결과 배열을 초기화한다.
- 각 숫자에 대해 아래 절차를 반복한다.
x보다 큰 수를 하나씩 증가시키면서 확인한다.
비트 차이를 계산하고, 1의 개수가 2개 이하인지 확인한다.
조건을 만족하는 첫 번째 수를 찾으면 결과 배열에 저장한다.
완성 코드 - 1 : 실패(시간 초과)
public class Test_55_NoMoreThan2Bits {
public long[] solution(long[] numbers) {
long[] answer = new long[numbers.length];
for (int i = 0; i < numbers.length; i++) {
answer[i] = findNextNum(numbers[i]);
}
return answer;
}
private long findNextNum(long x) {
long next = x + 1; // x보다 큰 수를 찾기 시작
while (true) {
// 비트 차이를 계산
long diff = x ^ next;
// 1의 개수 세기
if (countNum(diff) <= 2) {
return next; // 조건을 만족하면 반환
}
next++; // 다음 숫자로 이동
}
}
private int countNum(long n) {
int count = 0;
while (n > 0) {
count += (n & 1); // 마지막 비트 확인
n >>= 1; // 오른쪽으로 비트 이동
}
return count;
}
}문제 접근 방법 - 2
더이상의 시간복잡도를 개선할 방법을 찾기 어려워 구글링으로 다른 사람들의 코드를 찾아본 결과 여러 방법들이 있었고
그 중 가장 직관적이면서 좋아보이는 방법을 발견했다.
시간복잡도 문제를 해결하기 위해
- 주어진 수가 짝수라면 무조건 1의 자리에 비트가 없기 때문에 1을 더한 값이 답이 된다.
- 주어진 수가 홀수라면 비트 끝부터 탐색하여 0이 나오는 지점으로부터 10 비트를 넣어준다면 답이 된다.
완성 코드 - 2
public class Test_55_NoMoreThan2Bits {
public long[] solution(long[] numbers) {
long[] answer = new long[numbers.length];
for (int i = 0; i<numbers.length; i++) {
long result = numbers[i];
String target = Long.toBinaryString(numbers[i]);
if (result % 2 == 0) {
answer[i] = result + 1;
} else {
int idx = target.lastIndexOf("0");
if (idx == -1) {
String tmp = "10" + target.substring(1);
answer[i] = Long.parseLong(tmp, 2);
} else {
String tmp = target.substring(0, idx) + "10" + target.substring(idx + 2);
answer[i] = Long.parseLong(tmp, 2);
}
}
}
return answer;
}
}- Long.toBinaryString(num)과 Long.toString(num, 2)을 통해 쉽게 비트 변환이 가능하다.
- lastIndexOf을 활용하여 String에서 특정 값의 마지막 인덱스를 반환받을 수 있다. 혹시, 만족하는 값이 없다면 -1을 반환한다.
- substring을 활용하여 String에 대한 슬라이싱이 가능하게 된다.
- Long.parseLong(bit, 2)을 통해 비트를 다시 정수로 변환이 가능하다.
난 멋져!