Programmers / Level 2 / 2개 이하로 다른 비트 / JS

문제 간단설명

x가 주어지면 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 반환하면 된다.

 

제한 사항

• 1 <= numbers의 길이 <= 100,000
• 0 <= numbers의 모든 수 <= 10^15

 

실패 코드 (10번, 11번 테스트케이스 실패)

function solution(numbers) {
  const f = (n) => {
    if (n % 2 === 0) {
      return n + 1;
    }

    let bit = 1;
    // 가장 가까운 0을 찾는 반복문이다.
    while ((n & bit) !== 0) {
      // bit를 왼쪽으로 한 칸씩 이동시킨다.
      bit <<= 1;
    }
    return n + (bit >> 1);
  };

  const result = numbers.map((n) => f(n));

  return result;
}

 

전체적인 로직은 틀리지 않았다. 다만 총 11개의 테스트케이스에서 두가지 테스트케이스만 실패를 했는데, 아마 굉장히 큰 수 인것 같다. 찾아보니까, 32bit 이상의 값은 shift시에 그 이상의 bit는 삭제가 된다고 한다.

Javascript 32bit 이상 Number&Integer 계산하기 (BigInt)

 

따라서 전체적인 로직은 유지하되, 다음과 같이 바꾸어주니 성공이 가능했다.

 

성공 코드

function solution(numbers) {
  const f = (n) => {
    // 32비트가 넘어가게 되면 최상위 bit가 잘리게 되므로 BigInt로 변환한다.
    n = BigInt(n);
    if (n % 2n === 0n) {
      return n + 1n;
    }

    let bit = 1n;
    // 가장 오른쪽에 있는 0을 찾는 반복문이다.
    while ((n & bit) !== 0n) {
      // bit를 왼쪽으로 한 칸씩 이동시킨다.
      bit <<= 1n;
    }
    return n + (bit >> 1n);
  };

  const result = numbers.map((n) => f(n));

  return result;
}

 

제한사항에 number의 수가 최대 10^15이므로 32bit를 충분히 넘길 수 있는 수이다.

따라서 위와 같이 BigInt를 사용해주어 형변환과 계산 둘다 해주어야한다.

 

bit를 1~2개만 바꾸면서, 현재 수보다 크면서 그 중에서 가장 작은 수를 찾는 방법은 가장 오른쪽에 있는 0을 1로 바꾸어주면 된다.

 

가장 오른쪽이 0인지 확인하려면 어떻게 해야할까?

현재 수와 1을 bit AND(&) 연산을 해주면된다. 이 연산은 두 bit가 모두 1일 경우에만 1이 된다.

만약 마지막에서 두번째 bit가 0인지 확인하려면 1을 왼쪽으로 shift 한 후에 그 자리의 bit끼리 비교하면 된다.

계속 왼쪽으로 한칸씩 shift 하면서 비교를 했을 경우에 0이 나온다면 그 자리는 0인 bit이다.

 

그런데 만약 모든 bit가 1로만 이루어져 있다면?

위 반복문을 계속 돌면서 계속 왼쪽으로 shift하게 될 것이다. 그러면 결국 마지막엔 n의 자릿수를 넘게되고, 조건에 맞지 않으므로 while문을 종료하게 될 것이다.

 

예시로 7이라는 10진수가 있다고 해보자. 이 7은 2진수로 바꿨을 시에 111(2)가 된다.

모든 bit가 1이므로, 1을 왼쪽으로 계속 shift 하면서 마지막엔 7인 111(2)와 1000(2)를 비교하게 될 것이다.

111(2)는 0111(2)와 같으므로, 맨 앞자리수인 0과 1을 비교해서 0을 찾았기 때문에 반복문을 종료하게 된다.

이 특수한 상황에서 bit를 1~2개만 바꾸고 가장 가까운 큰 수는 맨 앞자리 bit에 1을 더해주는 것이다.

따라서 111(2) + 100(2) = 1011(2) = 11이 된다.

 

따로 처리해주지 않아도 같은 로직으로 가능하지만, 이러한 엣지 케이스도 생각하면 좋을 것 같다.