[4. 기본자료형] 4.4 같은 무게를 가진 가장 가까운 정수 찾기

---

Q 4.4 같은 무게를 가진 가장 가까운 정수 찾기

92의 2진수는 0101 1100 이며,
음이 아닌 어떤 정수x의 무게를 2진수로 표현된 정수의 1로 세팅된 비트의 개수라고 할때,
92의 무게는 4이다.

이때 음이 아닌 정수x와 무게는 같지만 x와의 차이 즉, | y - x | 가 최소가 되는 y를 반환하는 코드를 작성하시오.
Ex) x=6 일때 (6 은 0110 ->무게 : 2) 5를 반환한다. (5는 0101 -> 무게 : 2)

---

단순한 방법으로는 x-1, x+1, x-2, x+2 와 같이 x와 인접한 모든 수와 비교해서 무게가 같은 값을 바로 반환하는 방법이다. 이는 입력 숫자에 따라 비효율적일 수 있다. 이때 시간 복잡도는 x의 값만큼 으로 x가 1억이 넘어가면 1억을 다 해야한다.
따라서 휴리스틱한 방법을 사용하기 위해 몇가지 생각을 해보면 다음과 같다.
10 -> 01, 0111->1011 의 숫자가 | y - x |가 최소이며 무게가 같은 예시이다.
0과 1이 연속하지 않는 가장 오른쪽 지점에서 두 비트를 스왑하게 되면 무게는 같고 | y - x | 의 차이가 최소가 된다.

코드와 코딩결과는 다음과 같다.

시간복잡도 O(n) 단,n은 비트길이

6 (110) -> 5(101) 출력