프로그래머스: 2개 이하로 다른 비트

2개 이하로 다른 비트

numbers 배열의 요소인 양의 정수 x에 대하여, x보다 크고 x와 비트(bit)가 1~2개 다른 수들 중에서 제일 작은 수를 담은 배열을 반환하기

제한 조건
1 ≤ numbers.length ≤ $10^5$
1 ≤ x ≤ $10^{15}$

알고리즘 구상하기

시간복잡도를 줄이는데 집중한다.
numbers의 길이는 최대 $10^5$ 이다. 이는 연산을 수행할 요소들이 최대 $10^5$ 개 존재한다는 의미로, 이에 따라 시간복잡도 O(n)으로 풀이하는 것에 집중해야 한다.

규칙을 찾는다.
시간복잡도를 줄이기 위해서는 비트로 변환한 수들의 규칙을 찾아서 이를 효율적으로 풀이할 방법을 고민해야 한다.

이에 따라, 우선 x의 범위인 수 중에서 가장 작은 수부터 차례대로 나열하여 정답을 구하고 이들 간의 공통점을 고민하였다. 이를 표로 표현하면 다음과 같다.

10진수	비트(bit)
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111
16	10000
17	10001
18	10010
19	10011
20	10100

대부분의 경우, 자기 자신보다 1 큰 수가 문제에서 요구하는 값이었다.

그러나 10진수를 기준으로, 4로 나누었을때 나머지가 3이 되는 수들은(3, 7, 11, 15…) 자신보다 1 큰 수가 문제의 조건에 부합하지 않았다.

이들의 공통점은 비트의 길이가 늘어나거나 중간 자리의 비트가 변경되면서, 기존 비트와 다른 수가 3개 이상이 된 점이었다.

위의 경우에 해당하는 수들은 아래의 두 가지 규칙으로 나누어졌다.

첫번째 규칙는 비트가 모두 1로 이루어진 케이스였는데, 가장 큰 자리의 1이 0이 되고 비트의 길이가 1 늘어난 형태가 문제에서 찾는 값이었다.

두번째 규칙은 비트의 중간 자리 수에 ‘01’이 존재하고 이를 기준으로 오른쪽에 해당하는 낮은 자리 수들은 1로 채워진 경우에 적용할 수 있었다.
이 수들은 중간 자리 수의 ‘01’를 ‘10’으로 변환한 수가 문제에서 요구한 정답이었다.

x	answer
1111	10111
100111	101011

이러한 규칙을 토대로, 4로 나눈 나머지가 3인 수들을 별도로 체크하여 2진수로 변환한 각각의 비트를 split로 분리했다.

그리고 이를 순회하여 비트가 모두 1이라면 첫번째 규칙을, 비트가 2라면 두번째 규칙을 적용하여 정답을 찾았다.

이는 문제에서 주어진 조건 중 x가 $10^{15}$ 보다 작다는 점을 이용한 것으로, 비트로 변환했을때 실제로 순회하는 길이는 50에 불과하기 때문에 중첩 반복문을 이용하여도 시간복잡도 측면에서 문제가 없었다.

[JavaScript]

function solution(numbers) {
  const answer = numbers.map((number) => {
    const bitNumber = number.toString(2);
    const numberArray = bitNumber.split("");
    if (number % 4 === 3) {
      const containedOnes = [];
      while (numberArray.length > 0) {
        const lastNumber = Number(numberArray.pop());
        if (lastNumber !== 1) {
          break;
        }
        containedOnes.push(lastNumber);
      }
      return number + 2 ** (containedOnes.length - 1);
    }
    return number + 1;
  });
  return answer;
}