https://programmers.co.kr/learn/courses/30/lessons/77885
코딩테스트 연습 - 2개 이하로 다른 비트
programmers.co.kr
문제 설명
양의 정수 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
풀이코드
class 두개_이하로_다른_비트 {
static class Solution {
public long[] solution(long[] numbers) {
int N = numbers.length;
long[] answer = new long[N];
int n = 0;
for(long num : numbers) {
if((num&1)==0) {
answer[n++]=num+1;
}else {
loop:
for(long i = 1; i<( num <<2
); i = i<<1) {
if((i&num)==0) {
num =num|i;
for(long j = i>>1;j>0; j= j>>1) {
if((num&j)==j) {
answer[n++] = num-j;
break loop;
}
}
}
}
}
}
return answer;
}
}
public static void main(String[] args) {
long[] s = new Solution().solution(new long[] {2,7,61,43});
System.out.println(Arrays.toString(s));
}
}
풀이 코드 2
class Solution {
public long[] solution(long[] numbers) {
long[] answer = numbers.clone();
for(int i = 0; i< answer.length; i++){
answer[i]++;
answer[i] += (answer[i]^numbers[i])>>2;
}
return answer;
}
}1번 풀이 코드로 힘들게 힘들게 풀고 있었는데, 다 풀고 난 뒤 답에서 이렇게 쉬운 코드를 보았다.
우선 간단한 2번 코드부터 보자면,
먼저, 우선, answer에 기존의 numbers의 값을 복사해둔다.
그럼 그 값에는 answer와 같은 값이 들어있다.
이 값들을 계산하게 되는데, 조건 1번쨰 x보다 크고를 수행한다.
우선 answer에 1을 더해줌으로써 x보다 크고가 성립된다.
그렇다면, 예시를 31을 들어보면 011111 => 100000이 된다.
이 값은 가장 뒤쪽에 있는 0을 하나 1로 바꿔주게 되는데, 이것은 그 뒤에 모든 값들은 answer에 담긴 값은 0이라는 것과, numbers에 담긴 값은 1이라는 것을 알 수 있다.
그렇다면,
011111
^ 100000
-------------
111111
가 되는데, 100000뒤에 10 은 그대로 두고 그 뒤에 있는 값(2개를 뺸)만 1111로 바꾸어 주면 101111로 011111보다 크면서
비트 차이가 1~2개가 나는 가장 작은 값이 된다.
그렇기 때문에
answer[i]^numbers[i]로 그 뒤에 차이나는 자리수를 계산하고, 2진수에서 2칸만큼을 제외하고, answer[i]에 더하게 된다.
만약 짝수인 경우라면, 100 => 101 로 맨 뒷자리만 바뀌어서
100^101 = 1 // 1을 <<2 shift하면 0으로 answer는 그대로 유지된다.
그냥 2번 풀이만 이해해도 충분할 거 같다.