2개 이하로 다른 비트

2026.06.30

문제 풀이

1차 실행 오류

---

81.8/100

시간 초과 오류 발생

---

class Solution {
    public long[] solution(long[] numbers) {
        int len = numbers.length;
        long result[] = new long[len];
        
        for (int i = 0; i < len; i++) {
            long n = numbers[i];
            long index = n + 1;
            
            while(true) {
                long diff = Long.bitCount(n ^ index);
                if (diff <= 2) {
                    result[i] = index;
                    break;
                }
                index++;
            }
        }
                
        return result;
    }
}

AI 코드

---

처음 코드를 보고 말문이 막혔다.

서로 다른 비트가 2개 이하인 수 중에서 가장 작은 수를 찾는 경우는 2개가 존재

1) 0인 비트 중에서 가장 최하위 비트를 1로 바꿈
2) 1의 개수가 같은 수 중에서 바로 다음으로 큰 수(snoob알고리즘)

bitCount()를 이용해서 풀면 될 것 같다는 생각과 동시에
n과 numbers의 범위를 보고 안될 것 같다는 예상은 역시 틀리지 않았다.

해당 알고리즘은 해당 알고리즘은 맨땅에서 즉석으로 생각해내는 것이 아닌
숙지하고 있는 상태에서 적용하는 방식으로 사용해야 한다.

유도 과정을 이해하고 다른 문제에 적용할 수 있다면 됨

---

class Solution {
    public long[] solution(long[] numbers) {
        int len = numbers.length;
        long[] result = new long[len];

        for (int i = 0; i < len; i++) {
            result[i] = nextWithDiffAtMost2(numbers[i]);
        }

        return result;
    }

    private long nextWithDiffAtMost2(long n) {
        if (n == 0) return 1L;

        // 후보 A: 가장 낮은 0비트를 1로 set (diff = 1)
        long lowestZeroBit = (~n) & (n + 1);
        long candidateA = n | lowestZeroBit;

        // 후보 B: 같은 popcount를 가지는 바로 다음 큰 수 (diff = 2, snoob 알고리즘)
        long smallest = n & -n;
        long ripple = n + smallest;
        long ones = n ^ ripple;
        ones = (ones >> 2) / smallest;
        long candidateB = ripple | ones;

        return Math.min(candidateA, candidateB);
    }
}