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

비트 연산 문제 - 내가 완전히 잘못 접근한 케이스

문제를 제대로 안 읽고 시작한 게 문제였음

이 문제 처음 봤을 때 그냥 "x보다 크고 비트가 1~2개 다른 수" 찾는 거라고 생각했는데, 실제로는 "가장 작은 수"를 찾는 게 핵심이었음. 문제 제대로 안 읽고 바로 코딩 시작한 게 패망의 시작이었음.

내가 한 무식한 방법

function findNextNumber(x) {
  const xBig = BigInt(x);
  const limit = xBig + 100000n;

  for (let candidate = xBig + 1n; candidate <= limit; candidate++) {
    let diffCount = bitCountBigInt(xBig, candidate);
    if (diffCount >= 1 && diffCount <= 2) {
      return Number(candidate);
    }
  }
  return -1;
}

이거 완전 무식한 방법임. 그냥 하나씩 다 확인하면서 비트 차이 세는 거. 시간복잡도도 O(k × m)이고 비효율적임.

정답 코드 (진짜 똑똑한 방법)

function solution(numbers) {
  var answer = [];
  numbers.forEach((number) => {
    let str = "0" + number.toString(2);
    const l = str.length;
    if (str[l - 1] === "0") {
      answer.push(number + 1);
    } else {
      for (let i = str.length; i >= 0; i--) {
        if (str[i] === "0") {
          answer.push(
            parseInt(
              str.substring(0, i) + "1" + "0" + str.substring(i + 2, l),
              2
            )
          );
          break;
        }
      }
    }
  });
  return answer;
}

이거 보니까 완전 다르게 접근함. 패턴을 찾아서 해결한 거임.

어떻게 작동하는지

마지막 비트가 0인 경우

2 (10) → 3 (11)
그냥 +1 하면 됨. 비트 차이 1개고 가장 작은 수임.

마지막 비트가 1인 경우

7 (111) → 11 (1011)
오른쪽부터 첫 번째 0 찾아서 그걸 1로 바꾸고 그 다음을 0으로 바꿈.
0111 → 1011 이렇게 변환.

왜 이게 맞는지

마지막 비트가 0이면 그냥 +1 하는 게 가장 작은 수임. 비트 차이도 1개고.

마지막 비트가 1이면 연속된 1들의 패턴을 바꿔야 함. ...0111 이런 식으로 되어 있으면 ...1011로 바꾸는 게 가장 작은 수가 됨.

시간복잡도 차이

방법	시간복잡도	설명
내 방법	O(k × m)	하나씩 다 확인
정답	O(log n × m)	비트 길이만큼만 확인

교훈

1. 문제 제대로 읽기 - "가장 작은 수"라는 조건을 놓치면 안 됨
2. 패턴 찾기 - 비트 연산 문제는 수학적 패턴이 있음
3. 무식하게 접근하지 말기 - 순차 탐색보다는 패턴을 찾아서 해결

결국 문제를 제대로 이해하고 수학적 패턴을 찾는 게 핵심이었음. 나는 그냥 무식하게 하나씩 확인했는데, 정답은 패턴을 찾아서 효율적으로 해결한 거임.