[프로그래머스] 2개 이하로 다른 비트 (Java) - 비트 연산으로 풀기

📌 핵심 요약

• 짝수는 그냥 마지막 비트 0을 1로 바꾸면 끝 (x + 1)
• 홀수는 좀 복잡한데, 뒤에서부터 첫 번째 0을 찾아 1로 바꾸고 그 옆자리 1을 0으로 내려야 함
• 이걸 문자열로 안 풀고 ~x & (x + 1) 한 줄로 처리한 게 이번 풀이의 포인트

 

목차

PROGRAMMERS #77885

2개 이하로 다른 비트

1 ≤ numbers.length ≤ 10⁵ · 0 ≤ numbers[i] ≤ 10¹⁵

난이도: Level 2

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
: x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. 

numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

풀이 과정

1. numbers를 돌면서 각 x가 짝수인지 홀수인지 본다.
2. 짝수면 그냥 x+1.
3. 홀수면 비트 연산으로 뒤에서부터 첫 0을 찾고, 그 자리는 1로 바로 오른쪽 1은 0으로 바꿔준다.

1 짝수와 홀수, 왜 나눠서 봐야 하나

처음 문제를 봤을 때는 산술적으로 접근하려다가 막혔는데, 이진수로 바꿔서 보니까 패턴이 바로 보였습니다.

짝수인 경우

짝수는 이진수 마지막 자리가 항상 0입니다.

4 = 100인데, 이 마지막 0을 1로 바꾸면 101 = 5가 됩니다.

4보다 큰 수 중에 비트 1개만 다르면서 가장 작은 값이 바로 5고요.

그러니까 짝수는 마지막 비트만 0→1로 바꿔주면 끝이고, 결과적으로 x + 1이랑 똑같습니다.

홀수인 경우

홀수는 마지막 비트가 이미 1이라서 짝수처럼 단순하게 안 됩니다.

7 = 0111인데 마지막 비트를 만지면 오히려 값이 줄어드니까, 더 큰 수를 만들려면 앞쪽(높은 자리)에 있는 0을 찾아서 1로 바꿔야 합니다.

7에서 뒤에서부터 처음 나오는 0은 맨 앞자리입니다. 거기를 1로 바꾸면 1111 = 15가 되는데 최소값이 아닙니다.

최소값을 만들려면 방금 0→1로 바꾼 자리 바로 오른쪽에 있는 1을 다시 0으로 내려줘야 합니다.

1111(15)에서 그 자리를 0으로 내리면 1011 = 11이 나옵니다.

2 비트 연산으로 구현하기

문자열로 이진수 변환해서 자리 찾는 방법도 있긴 한데, 비트 연산만으로 "뒤에서부터 첫 0의 위치"를 한 번에 찾을 수 있습니다.

핵심은 ~x & (x + 1) 이 한 줄입니다.

 

Java — Solution.java

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

        for (int i = 0; i < numbers.length; i++) {
            long x = numbers[i];

            // 1. 짝수인 경우
            if (x % 2 == 0) {
                answer[i] = x + 1;
            } else {
                // 2. 홀수인 경우
                // 가장 뒤에 있는 '0'의 위치를 찾는 비트 연산
                long lastZero = ~x & (x + 1);

                // 가장 뒤의 '0'을 '1'로 바꾸고, 그 오른쪽 비트('1')를 '0'으로 변경
                answer[i] = (x | lastZero) & ~(lastZero >> 1);
            }
        }

        return answer;
    }
}

왜 ~x & (x + 1)이 "가장 뒤의 0"을 찾아낼까

이진수에서 1을 더하면, 뒤에서부터 1인 비트들은 전부 받아올림(Carry)이 발생하면서 0으로 바뀝니다.

이 올림은 처음으로 0을 만날 때까지 계속 올라갑니다. 11(01011)에 1을 더하면 12(01100)이 되는 것처럼요.

 

~x는 x의 비트를 전부 반전시킨 값입니다.

x가 01011이면 ~x는 10100(하위 비트만 보면)이 되는데, 결국 원래 0이었던 자리만 1로 표시된 셈입니다.

x + 1인 01100과 ~x를 AND로 묶으면 둘 다 1인 자리, 즉 원래 0이었던 자리 중에서 가장 낮은 자리만 딱 남습니다. 이게 우리가 찾던 "가장 뒤에 있는 0의 위치"입니다.

단계	x = 11	설명
x	01011	원본 값
x + 1	01100	마지막 0이 1로 바뀌는 자리까지 carry 전파
~x	10100	모든 비트 반전 (0이었던 자리만 1)
lastZero = ~x & (x+1)	00100	"가장 뒤의 0" 위치만 남은 비트마스크

최종 답: (x | lastZero) & ~(lastZero >> 1)

1. x | lastZero로 lastZero 자리를 1로 켭니다. (01011) | 00100 = 01111
2. lastZero >> 1로 그 바로 오른쪽 비트를 가리키는 마스크를 만듭니다. 00100 >> 1 = 00010
3. ~(lastZero >> 1)로 그 자리만 0이고 나머지는 1인 마스크가 됩니다.
4. AND 연산으로 해당 자리를 꺼줍니다. 01111 & 11101 = 01101 (13)

💡

lastZero 오른쪽 비트는 왜 항상 1일까

lastZero가 "가장 뒤에 있는 0"이라는 건, 그보다 오른쪽 자리는 다 1이라는 뜻입니다. 그래서 lastZero >> 1 자리는 항상 1이 보장되어 있고, 안심하고 0으로 꺼도 됩니다.

3 시간 복잡도

원소 하나당 비트 연산 몇 번(AND, OR, NOT, shift)만 도니까 O(1)이고, 전체로 보면 O(N)입니다.

이진수 문자열 만들어서 인덱스 찾는 방식보다 훨씬 가볍습니다.

⚠️

자료형 조심

numbers[i]가 최대 10¹⁵까지 가니까 int로는 못 버티고 long을 써야 합니다. 처음부터 long[]으로 잡아둔 덕에 오버플로 걱정 없이 넘어갔습니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.