C++로 K에 가장 가까운 부분 배열 비트 AND의 최소 차이 구하기

이 문제에서는 크기가 n인 배열 arr[]와 정수 k가 하나씩 주어집니다. 우리가 구해야 하는 것은 배열 안에서 인덱스 i부터 j까지에 해당하는 부분 배열(subarray)을 선택해 그 모든 원소의 비트 AND(bitwise AND)를 계산한 뒤, 그 값과 k 사이의 차이, 즉 |k − (비트 AND 값)|이 최소가 되는 경우를 찾아 그 최솟값을 출력하는 것입니다.

예제로 문제 이해하기

입력: arr[] = {5, 1}, k = 2

출력: 1

배열 {5, 1}에서 만들 수 있는 부분 배열은 {5}, {1}, {5, 1} 세 가지이며, 각각의 비트 AND 값은 5, 1, 그리고 5 & 1 = 1입니다. 따라서 |2 − 5| = 3, |2 − 1| = 1이 되고, 최종 답은 1입니다.

방법 1: 완전 탐색(Brute Force)

가장 직관적인 풀이는 모든 부분 배열의 비트 AND를 직접 계산한 뒤, 각 값 X에 대해 |k − X|를 구하고 그중 최솟값을 찾는 것입니다.

1단계: 가능한 모든 부분 배열에 대한 비트 AND 값을 구합니다.
2단계: 앞에서 구한 각 값 X에 대해 |k − X|를 계산합니다.
3단계: 지금까지 나온 최솟값을 min 변수에 저장해 둡니다.
4단계: 모든 탐색이 끝나면 min 값을 출력합니다.

이 방식은 시작 인덱스와 끝 인덱스를 정하는 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다.

구현 코드

#include <iostream>
using namespace std;

int CalcBitwiseANDClosestK(int arr[], int n, int k){
    int minimum = 1000;
    for (int i = 0; i < n; i++) {
        int X = arr[i];
        for (int j = i; j < n; j++) {
            X &= arr[j];
            minimum = min(minimum, abs(k - X));
        }
    }
    return minimum;
}

int main() {
    int arr[] = { 1, 6, 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "부분 배열의 비트 AND와 K 사이의 최소 차이 값은 " << CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

실행 결과

부분 배열의 비트 AND와 K 사이의 최소 차이 값은 1입니다.

방법 2: 비트 AND 연산의 특성을 활용한 최적화

더 효율적인 해결책은 비트 AND 연산의 고유한 성질을 관찰하는 것입니다. 부분 배열에 원소가 하나씩 추가될 때마다 AND 값은 절대 커지지 않으며, 그대로이거나 작아질 수만 있습니다. AND 연산은 이미 켜져 있는 비트를 끄거나 유지할 수는 있지만, 꺼져 있는 비트를 다시 켜지는 않기 때문입니다.

이 성질을 활용하면 다음과 같이 최적화할 수 있습니다. 어느 시점에서 부분 배열의 비트 AND 값이 k 이하가 되었다면(X ≤ k), 그 상태에서 원소를 더 추가해도 AND 값은 줄어들거나 그대로이므로 |k − X| 역시 더 이상 작아질 수 없습니다. 따라서 최솟값을 갱신한 후에는 해당 시작 인덱스에 대한 탐색을 조기에 중단(break)하여 불필요한 연산을 줄일 수 있습니다.

구현 코드

#include <iostream>
using namespace std;

int CalcBitwiseANDClosestK(int arr[], int n, int k){
    int minimum = 1000000;
    for (int i = 0; i < n; i++) {
        int BitwiseAND = arr[i];
        for (int j = i; j < n; j++) {
            BitwiseAND &= arr[j];
            minimum = min(minimum, abs(k - BitwiseAND));
            if (BitwiseAND <= k)
                break;
        }
    }
    return minimum;
}

int main() {
    int arr[] = { 1, 6, 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "부분 배열의 비트 AND와 K 사이의 최소 차이 값은 " << CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

실행 결과

부분 배열의 비트 AND와 K 사이의 최소 차이 값은 1입니다.

정리

두 방법 모두 동일한 정답을 출력하지만, 두 번째 접근 방식은 비트 AND 값이 k 이하로 내려가는 순간 내부 반복문을 즉시 멈추기 때문에 실제로 수행되는 연산 횟수가 크게 줄어듭니다. 이처럼 비트 연산의 단조 감소(monotonic decrease) 특성을 파악해 두면, 부분 배열과 관련된 다양한 문제를 훨씬 효율적으로 해결할 수 있습니다.