프로그래머스 | Level 2 | 2개 이하로 다른 비트

Aug 28, 2024

Published byJynn

999

Programmers | Level 2 | 2개 이하로 다른 비트

Problems

📘 Src: Programmers
🗂️ Cat: Bit Manipulation

󰧭 Description

양의 정수 x에 대한 함수 f(x)는 x보다 크고, x와 비트가 1~2개 다른 수들 중에서 가장 작은 수를 찾는 함수입니다. 예를 들어 f(2) = 3이고, f(7) = 11입니다. 각 수가 담긴 배열 numbers가 주어질 때, 각 수에 대한 f(x) 값을 배열로 반환하는 문제입니다.

예를 들어, f(2) = 3입니다. 아래 표를 보면 2보다 큰 수들 중에서 비트가 2개 이하로 다른 가장 작은 수가 3입니다:

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

또한, f(7) = 11입니다. 아래 표에서 7보다 큰 수들 중에서 비트가 2개 이하로 다른 가장 작은 수는 11입니다:

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

 Constraints

1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 10^15

󰦕 Examples

numbers	result
`[2, 7]`	`[3, 11]`

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] result = new long[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            long number = numbers[i];
            
            // 짝수 처리
            if (number % 2 == 0) {
                result[i] = number + 1;
                continue;
            }
            
            // 홀수 처리
            long bitMask = 1;
            // 첫 번째 비트 조작
            while ((number & bitMask) != 0) {  // 가장 오른쪽의 0 탐색
                bitMask <<= 1;
            }
            number = (number | bitMask);  // 가장 오른쪽 0 비트를 1 비트로 변경
            
            // 두 번째 비트 조작
            bitMask = (bitMask >> 1);  // 비트마스크 오른쪽으로 1칸 이동
            number = (number & ~bitMask);  // 비트마스크 위치의 비트 반전
            
            result[i] = number;  // 최종 연산 결과 저장
        }        
        return result;
    }
}

 Approach

이 문제는 주어진 x보다 큰 수 중에서 비트가 1 ~ 2개만 다른 가장 작은 수를 찾아야 하는 비트 연산 문제입니다. 각 숫자에 대해 효율적으로 조건을 만족하는 수를 구해야 하며, 비트 연산을 통해 이 문제를 해결할 수 있습니다. 비트 연산은 숫자의 이진 표현을 조작하여 원하는 결과를 빠르고 정확하게 도출할 수 있는 매우 유용한 도구입니다.

비트 연산은 컴퓨터 내부에서 이진수로 표현된 값을 다루는 연산입니다. 비트 연산자는 각 비트 단위로 연산을 수행하며, 매우 빠르게 계산을 처리할 수 있습니다. 아래는 자주 사용하는 비트 연산자들입니다.

Operator	Description	Example
`&`	AND: 두 비트 모두 `1`일 때 `1`	`1101 & 1011 == 1001`
`\|`	OR: 두 비트 중 하나라도 `1`이면 `1`	`1101 \| 1011 == 1111`
`^`	XOR: 두 비트가 서로 다를 때 `1`	`1101 ^ 1011 == 0110`
`~`	NOT: 비트를 반전시킴 (0 → 1, 1 → 0)	`~1101 == 0010`
`<<`	LEFT SHIFT: 비트를 왼쪽으로 이동	`1101 << 1 == 11010`
`>>`	RIGHT SHIFT: 비트를 오른쪽으로 이동	`1101 >> 1 == 0110`

1. 문제 분석

이 문제는 입력된 숫자 보다 크면서, 이진수 변환시 비트가 1 ~ 2개가 다른 수들 중 가장 작은 수를 찾는 것이 목표입니다. 문제는 크게 두 가지 경우로 나눌 수 있습니다.

짝수인 경우: 짝수는 마지막 비트가 0으로 끝납니다. 이 경우, x + 1이 항상 x보다 비트가 1개 다른 가장 작은 수가 됩니다. 예를 들어, x = 2(이진수 10)인 경우, x + 1 = 3(이진수 11)이 됩니다. 두 수의 비트 차이는 1개이므로 조건을 만족합니다.
홀수인 경우: 홀수는 마지막 비트가 1로 끝납니다. 이 경우 x + 1을 하면 비트 차이가 2개 이상이 될 수 있으므로, 보다 복잡한 처리가 필요합니다. 이때 비트마스크 개념을 사용하여 가장 오른쪽에 있는 0 비트를 찾아 1로 바꾸고, 이후 비트를 조정해 비트 차이가 1~2개인 가장 작은 수를 구합니다.

비트마스크는 이진수 값 중 특정 비트의 위치를 추적하거나 조작하기 위해 사용하는 이진수 값입니다. 예를 들어, bitMask = 1로 설정하면 이진수 000...0001을 의미하며, 대상 숫자와의 AND 연산을 통해 숫자의 특정 비트가 1인지 0인지 확인할 수 있습니다.

2. 짝수인 경우

짝수의 경우 비트가 1개만 다른 가장 작은 수는 간단히 x + 1이 됩니다. 이진수로 변환했을 때, 짝수는 항상 마지막 비트가 0이므로 그 다음 큰 수는 비트 차이가 1개인 수입니다.

Solution.java

// 짝수인 경우
if (number % 2 == 0) {
    result[i] = number + 1;  // 비트 차이 1개로 가장 작은 숫자는 num + 1
    continue;
}

이러한 방식으로 짝수는 x + 1만 계산해주면 바로 결과를 얻을 수 있습니다.

3. 첫 번째 비트 조작

홀수의 경우, 단순히 x + 1을 하면 비트 차이가 2개 이상 발생할 수 있습니다. 이를 해결하기 위해서는 비트 차이가 1개인 가장 작은 숫자를 먼저 찾아야 합니다. 이 값은 이진수에서 가장 오른쪽에 있는 0을 1로 바꾸는 방식으로 구할 수 있습니다.

예를 들어, 숫자 7의 이진수는 0111이고 가장 오른쪽에 있는 0을 1로 바꾸면 1111이 됩니다. 이는 10진수로 15에 해당하며, 7보다 크고 비트 차이가 1개인 가장 작은 수입니다. 이 과정은 비트마스크를 활용하여 다음과 같은 방식으로 수행됩니다:

단계	bitMask	AND 연산	결과	설명
1	`0001`	`0111 & 0001`	`0001`	첫 번째 비트 확인
2	`0010`	`0111 & 0010`	`0010`	두 번째 비트 확인
3	`0100`	`0111 & 0100`	`0100`	세 번째 비트 확인
4	`1000`	`0111 & 1000`	`0000`	`0` 비트 발견

이 과정을 코드로 구현하면 아래와 같습니다:

Solution.java

long bitMask = 1;
while ((number & bitMask) != 0) {
    bitMask <<= 1;  // 가장 오른쪽의 0을 찾기 위해 bitMask를 왼쪽으로 이동
}

// 가장 오른쪽에 있는 0 비트를 1로 변경
number = number | bitMask;

이 과정을 통해 주어진 숫자 보다 크면서 비트 수가 하나 다른 숫자 중 가장 작은 수를 계산할 수 있습니다.

4. 두 번째 비트 조작

다음은 이전 과정의 결과에 추가로 하나의 비트를 더 변경하여 비트 차이가 2개인 가장 작은 수를 찾는 과정입니다. 현재 비트마스크 위치에서 바로 오른쪽에 있는 1 비트를 0으로 변경함으로써 비트 차이가 2개인 가장 작은 수를 만들 수 있습니다.

Solution.java

bitMask = bitMask >> 1;  // 비트마스크를 오른쪽으로 한 칸 이동
number = number & ~bitMask;  // 비트마스크 위치의 비트를 0으로 변경

5. 결과 리턴

배열에 담긴 모든 숫자에 대해서 위 연산을 적용하여 얻은 결과를 배열에 저장하고 이를 반환합니다.

󰄉 Complexity

⏳ TC: O(n)
💾 SC: O(n)

이 알고리즘은 주어진 배열의 각 숫자에 대해 비트 연산을 수행하므로, 시간 복잡도는 O(n)입니다. n은 주어진 배열의 크기입니다. 또한, 결과를 저장하기 위해 n 크기의 배열을 사용하므로 공간 복잡도도 O(n)입니다.

Algorithm
Bit Manipulation