[스위프트 알고리즘] 프로그래머스: 2개 이하로 다른 비트

문제

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

문제 설명

양의 정수 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씩 더해가면서 가장 처음 등장하는 비트의 차이가 1이나 2인 숫자를 찾아내었습니다. 하지만 시간초과로 마지막 두 개의 테스트케이스를 통과하지 못했고, 고민을 하다가 구글링을 통해 힌트를 얻어 풀게 되었습니다. 

 

먼저 차이가 1이나 2가 나는 가장 작은 수를 구할 때, 기준 숫자가 짝수인 경우에는 바로 다음 숫자가 차이가 1이 나는 가장 작은 숫자가 됩니다. 2진수로 표현했을 때 짝수는 LSB가 항상 0이기 때문에, 짝수의 바로 다음 숫자는 0을 1로 만드는 수 입니다. 따라서 짝수의 경우에는 기준 숫자에서 1을 더한 숫자가 정답입니다.

 

홀수의 경우에는 조금 복잡합니다. 홀수는 마지막 비트인 LSB가 항상 1입니다. 따라서 2진수로 변환했을 때 최소한의 변화로 1을 0으로 만드는 숫자를 골라내야합니다. 이를 위해 비트연산을 사용합니다. 비트연산을 통해 다음과 같은 로직으로 다음 숫자를 찾아낼 것입니다.

 

예를 들어, 알고자 하는 기준 숫자가 7(0000...(총 64비트)...0111) 이라고 해보겠습니다.

1. 현재 숫자의 2진수에 보수를 취하고 현재 숫자에 1을 더한 값의 2진수와 AND 연산을 취한다.
   • 0000...0111의 보수는 1111...1000 입니다.
   • 7에 1을 더한 값은 8이고, 2진수로 변환하면 0000...1000 이 됩니다.
   • 현재 숫자인 0000...0111과 1111...1000의 AND 연산을 수행하면 0000...0000 이 됩니다.
     • 여기서 1000의 1은 LSB를 기준으로 가장 가까이에 있는 0을 의미합니다. 즉, 7을 2진수로 바꿨을 때 가장 오른쪽에서 가장 가까이에 있는 0비트가 4번째 (0111) 이고, 이곳을 1로 만들고 1중 하나를 0으로 만들면 2개를 바꿔 현재 숫자에서 가장 가까운 숫자를 구할 수 있습니다.
   • 결국 이 단계에서 한 작업은 기준 숫자에서 어떤 0을 1로 바꿀지를 결정한 것입니다.
2. 이제 기준숫자와 위에서 구한숫자에 OR연산을 취합니다.
   • 0000...1000 과 0000...0111 의 OR 연산결과는 0000...1111 입니다. 이 값은 현재 비트로 얻을 수 있는 가장 큰 값이 됩니다.
   • 1단계에서 구한 이진수를 오른쪽으로 쉬프트하고 보수를 취하면 1단계에서 찾은 바꿀 0의 위치에서 가장 가까운 1은 0으로 만들고 나머지는 그대로 유지할 수 있습니다. 오른쪽으로 한 칸 이동시키는 이유는 이진수에서 기준점으로부터 오른쪽에 가장 가까운 1을 0으로 바꿔야 기준 숫자와 차이가 가장 적은 숫자를 만들 수 있기 때문입니다.
     • 1단계에서 구한 0000...1000을 오른쪽으로 한칸 쉬프트하면 0000...0100이 됩니다.
     • 이 결과에 보수를 취하면 1111...1011 을 얻습니다.
     • 현재 결과가 음수이기 때문에 양수 변환하기 위해서 2-1단계에서 얻은 가장 큰 값과 AND 연산을 수행합니다.
       • 0000...1111 과 1111...1011의 AND 연산결과는 0000...1011 입니다. 그리고 이 값이 주어진 숫자보다 큰 숫자들 중 가장 작은, 2개 이하의 비트 차이를 가지는 숫자가 됩니다.

코드