2개 이하로 다른 비트

문제

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다. x보다 크고, x와 비트가 1~2개 다른 수들 중에서 제일 작은 수. 정수 배열 numbers가 주어졌을 때, 각 수에 대한 함수 f의 값을 배열에 담아 반환하는 문제입니다.

• 입력: 정수 배열 numbers (길이 1 이상 100,000 이하, 원소는 10^15 이하의 양의 정수)
• 출력: 각 수에 대한 함수 f의 값을 담은 정수 배열

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

풀이 1: 2진수 문자열로 변환하여 탐색

숫자를 2진수 형태의 문자열(String)로 바꾼 뒤 규칙에 맞게 문자를 직접 교체해 주는 방식으로 구현이 가능합니다.

• 짝수인 경우:
  • 짝수는 2진수로 바꿨을 때 항상 맨 오른쪽 끝이 0입니다. (예: 2 -> 10, 4 -> 100)
  • 맨 끝의 0만 1로 바꿔주면 비트가 딱 1개만 다른 가장 작은 수가 됩니다. 즉, 그냥 1을 더해주면 끝납니다. (x + 1)
• 홀수인 경우:
  • 홀수는 무조건 맨 오른쪽 끝이 1입니다. (예: 7 -> 111, 11 -> 1011)
  • 홀수에서 비트를 1~2개만 바꾸어 만들 수 있는 가장 작은 큰 수는, 가장 오른쪽에 있는 '0'을 '1'로 바꾸고, 그 바로 오른쪽에 있던 '1'을 '0'으로 바꾸는 것입니다.
  • 예외 방지: 7(111)처럼 문자열에 '0'이 아예 없는 경우가 있습니다. 이를 안전하게 처리하기 위해 변환된 이진수 문자열 맨 앞에 강제로 "0"을 하나 붙여줍니다. ("0111")
  • lastIndexOf("0")을 이용해 가장 오른쪽에 있는 0의 위치를 찾고, substring으로 잘라내어 해당 0과 그 오른쪽 1을 "10"으로 교체합니다.

코드 1

class Solution {
    public long[] solution(long[] numbers) {
        long[] ans = new long[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            long x = numbers[i];
            
            // 1. 짝수인 경우: 맨 끝 0을 1로 바꾸는 것과 같으므로 단순히 +1
            if (x % 2 == 0) {
                ans[i] = x + 1;
            } 
            // 2. 홀수인 경우: 이진수 문자열로 변환하여 조작
            else {
                // 111(7) 같이 0이 없는 경우를 대비해 맨 앞에 0을 강제로 붙여줌
                String s = "0" + Long.toBinaryString(x);
                
                // 가장 오른쪽에 있는 0의 인덱스를 찾음
                int idx = s.lastIndexOf("0");
                
                // 찾은 0을 1로, 그 바로 오른쪽 1을 0으로 바꿈 (즉, "01" -> "10"으로 교체)
                String res = s.substring(0, idx) + "10" + s.substring(idx + 2);
                
                // 조작된 2진수 문자열을 다시 10진수 정수로 변환
                ans[i] = Long.parseLong(res, 2);
            }
        }
        
        return ans;
    }
}

풀이 2: 비트 연산 활용

문자열 변환은 이해하기 쉽지만 객체 생성 때문에 실행 시간이 약간 더 걸립니다. 만약 실행 속도를 극한으로 끌어올리고 싶다면, 풀이 1의 논리를 그대로 비트 시프트 연산으로 변환하여 O(1)의 속도로 해결할 수 있습니다.

• 홀수 규칙의 비트화: 가장 오른쪽에 있는 0의 위치(bit)를 찾기 위해 while문을 돌며 비트를 왼쪽으로 한 칸씩(<<= 1) 옮겨가며 확인합니다.
• 0의 위치를 찾았다면, x | bit로 해당 위치를 1로 켜주고, 그 바로 오른쪽 위치(bit >> 1)를 ~ 연산과 & 연산을 조합해 0으로 꺼줍니다.

코드 2

class Solution {
    public long[] solution(long[] numbers) {
        long[] ans = new long[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            long x = numbers[i];
            
            if (x % 2 == 0) {
                ans[i] = x + 1;
            } else {
                long bit = 1;
                
                // 오른쪽에서부터 연속된 1을 지나 처음 등장하는 0의 위치(bit) 찾기
                while ((x & bit) != 0) {
                    bit <<= 1;
                }
                
                // 해당 0 비트를 1로 켜고( | bit ), 바로 오른쪽 비트를 0으로 끔( & ~(bit >> 1) )
                ans[i] = (x | bit) & ~(bit >> 1);
            }
        }
        
        return ans;
    }
}

알고리즘 분류

수학 (Mathematics), 문자열 (String), 비트 조작 (Bit Manipulation)