[프로그래머스/자바] 2개 이하로 다른 비트

사진 클릭시 문제로 이동

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
3	000...0011	1
2	000...0010

• 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

• 문제 예시와 같습니다.

  ---

설명

간단하게 생각해서 입력받는 numbers부터 큰수를 다 살펴보고 XOR연산을 통해 그 값의 bitCount가 1또는 2인경우 답으로 살펴보았더니 시간초과가 발생했다.

따라서 숫자를 다 살펴보는 것은 안된다.

 

다르게 문제를 해결해야 하는데 문제에 힌트가 있다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

그러면 언제 비트가 1개 클때 제일 작은 수가 되고

2개 클때 제일 작은 수가 되는 것은 무엇일까?

 

바로 짝수와 홀수다.

1) 짝수인 경우,

n = 2 => 10

n= 4 => 100

n = 6 => 110

n = 8 => 1000

:

이런식으로 2진수로 변환하게 되는데 잘 생각해보면 끝자리가 모두 0인 것을 알 수 있다.

따라서 끝자리를 1로 바꾸면 비트가 1개 바뀌고 x보다 크면서 제일 작은 수가 된다.

이말을 다른 말로 하면 짝수인 경우 = 값 + 1 하면 된다는 말고 같다.

 

2) 홀수인 경우,

n = 3 =>  11 ==> 101

n = 5 => 101 ==> 110

n = 7 => 111 ==> 1011

n = 9 = > 1001 ==> 1010

n = 11 => 1011 ==> 1101 

n = 13 => 1101 ==> 1110

n = 15 => 1111 ==> 10111

:

이런식으로 2진수로 변환하게 된다.

이때 홀수가 두가지 경우로 나뉘게 되는데 모두1만 있는 수와 1과 0이 섞인수이다.

2-1) 모두 1비트만 있는경우

비트 1값을 바꾸면 값이 x보다 작아진다.

따라서 맨앞 비트를 0으로 바꾸는 대신 더 앞에 1비트를 추가해야 한다.

2-2) 0비트가 포함된경우

해당 값만 1비트로 바꾸면 물론 x보다는 커지지만 이값은 제일 작은 값이 되지 않는다. 

따라서 가장 먼저 나오는 0비트를 1로 바꾸는 대신 그 뒤에 있는 비트가 0으로 바뀌면 2개의 비트가 바뀌지만 제일 작은 값이 된다.

코드