C++로 두 개의 이진 배열의 XOR을 세 번째 배열과 일치시키는 최소 비트 반전 구하기

문제 설명

크기가 n인 0과 1로 구성된 세 개의 배열이 주어졌을 때, 첫 번째 배열과 두 번째 배열의 각 인덱스 비트를 XOR 연산한 결과가 세 번째 배열의 해당 인덱스 비트와 일치하도록 만들어야 합니다. 이때 필요한 최소 비트 반전(플립) 횟수를 구하는 것이 이 문제의 목표입니다.

단, 다음과 같은 제약 조건이 있습니다.

첫 번째 배열은 최대 p개의 비트만 반전할 수 있습니다.
두 번째 배열은 최대 q개의 비트만 반전할 수 있습니다.
배열 요소의 순서를 재배치하는 것은 허용되지 않습니다.

p = 2, q = 5인 경우를 예로 들어 보겠습니다.

arr1[] = {1, 0, 1, 1, 0, 1, 0}
arr2[] = {0, 1, 0, 1, 0, 0, 1}
arr3[] = {0, 1, 1, 0, 0, 0, 0}

각 인덱스별로 XOR 결과를 확인해 보면 다음과 같습니다.

인덱스 0: (arr1[0] ^ arr2[0]) = (1 ^ 0) = 1 → arr3[0](= 0)과 다르므로 반전 필요
인덱스 1: (arr1[1] ^ arr2[1]) = (0 ^ 1) = 1 → arr3[1](= 1)과 같으므로 반전 불필요
인덱스 2: (arr1[2] ^ arr2[2]) = (1 ^ 0) = 1 → arr3[2](= 1)과 같으므로 반전 불필요
인덱스 3: (arr1[3] ^ arr2[3]) = (1 ^ 1) = 0 → arr3[3](= 0)과 같으므로 반전 불필요
인덱스 4: (arr1[4] ^ arr2[4]) = (0 ^ 0) = 0 → arr3[4](= 0)과 같으므로 반전 불필요
인덱스 5: (arr1[5] ^ arr2[5]) = (1 ^ 0) = 1 → arr3[5](= 0)과 다르므로 반전 필요
인덱스 6: (arr1[6] ^ arr2[6]) = (0 ^ 1) = 1 → arr3[6](= 0)과 다르므로 반전 필요

따라서 총 3번의 반전이 필요하며, 이는 허용된 최대 반전 횟수(p + q = 7) 이내이므로 유효한 해답입니다.

알고리즘

문제 해결 접근 방식은 다음과 같습니다.

(arr1[i] ^ arr2[i]) == arr3[i]라면 반전이 필요하지 않으므로 그대로 진행합니다.
(arr1[i] ^ arr2[i]) != arr3[i]라면 반전이 필요합니다.
  a. arr3[i] == 0인 경우, 다음 조건 중 하나가 참입니다.
    i. (arr1[i] == 0) && (arr2[i] == 0)
    ii. (arr1[i] == 1) && (arr2[i] == 1)
  b. arr3[i] == 1인 경우, 다음 조건 중 하나가 참입니다.
    i. (arr1[i] == 0) && (arr2[i] == 1)
    ii. (arr1[i] == 1) && (arr2[i] == 0)
반전이 필요한 경우 arr1[i] 또는 arr2[i] 중 어느 한쪽을 반전하면 됩니다. 따라서 arr1과 arr2의 XOR을 arr3과 같게 만드는 데 필요한 총 반전 횟수는 p + q보다 작거나 같아야 한다는 결론에 도달합니다.

C++ 구현 예제

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getRequiredFlips(int *arr1, int *arr2, int *arr3, int n, int p, int q){
    int flips = 0;
    for (int i = 0; i < n; ++i) {
        if ((arr1[i] ^ arr2[i]) != arr3[i]) {
            ++flips;
        }
    }
    return flips <= (p + q) ? flips : -1;
}

int main(){
    int arr1[] = {1, 0, 1, 1, 0, 1, 0};
    int arr2[] = {0, 1, 0, 1, 0, 0, 1};
    int arr3[] = {0, 1, 1, 0, 0, 0, 0};
    int size = SIZE(arr1);
    cout << "Flips required: " << getRequiredFlips(arr1, arr2, arr3, size, 2, 5) << "\n";
    return 0;
}

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Flips required: 3

총 7개의 요소 중 인덱스 0, 5, 6에서 XOR 결과가 일치하지 않았으며, 필요한 반전 횟수 3회는 허용 범위(p + q = 7) 내에 있으므로 프로그램은 3을 반환합니다. 만약 필요한 반전 횟수가 p + q를 초과한다면 함수는 -1을 반환하여 주어진 조건 내에서는 해결이 불가능함을 나타냅니다.