개념
음이 아닌 정수로 구성된 배열 Arr[]가 주어졌을 때, 다음 식의 합계를 최소로 만드는 정수 X를 찾는 것이 이 글의 목표입니다.
(Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n-1] XOR X)
입력 예시
Arr[] = {3, 4, 5, 6, 7}출력 결과
X = 7, Sum = 10
접근 방법
배열의 모든 수를 이진수로 표현했을 때 각 비트 자리 'i'를 하나씩 검사하고, 해당 비트가 '1'로 설정된(set) 수의 개수를 셉니다. 이미 설정된 비트가 많을수록 XOR 연산 결과가 커져 오히려 합계를 증가시키는 요인이 되기 때문입니다.
따라서 특정 비트 자리에서 '1'로 설정된 수의 개수가 N/2보다 크다면, 그 비트를 '0'으로 만드는 것이 유리합니다. 반대로 개수가 N/2보다 작다면 해당 비트가 설정된 수가 적어 전체 합계에 큰 영향을 주지 않습니다.
여기서 XOR 연산의 핵심 성질을 활용합니다. 두 비트 A와 B가 서로 같으면 A XOR B의 결과는 '0'이 됩니다. 따라서 '1'로 설정된 수가 과반수를 넘는 비트 자리에는 찾고자 하는 수 X의 해당 비트를 '1'로 설정합니다. 그러면 (1 XOR 1) = 0이 되어 각 요소의 해당 비트가 0으로 바뀌고, 결과적으로 합계를 최소화할 수 있습니다.
예제 코드
// 접근 방식의 C++ 구현
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void findX1(int arr1[], int n1){
int* itr1 = max_element(arr1, arr1 + n1);
int p1 = log2(*itr1) + 1;
int X1 = 0;
for (int i = 0; i < p1; i++) {
int count1 = 0;
for (int j = 0; j < n1; j++) {
if (arr1[j] & (1 << i)) {
count1++;
}
}
if (count1 > (n1 / 2)) {
X1 += 1 << i;
}
}
long long int sum1 = 0;
for (int i = 0; i < n1; i++)
sum1 += (X1 ^ arr1[i]);
cout << "X = " << X1 << ", Sum = " << sum1;
}
// 실행 코드
int main(){
int arr1[] = { 3, 4, 5, 6, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
findX1(arr1, n1);
return 0;
}코드 동작 원리 살펴보기
입력 배열 {3, 4, 5, 6, 7}을 이진수로 표현하면 다음과 같습니다.
- 3 = 011
- 4 = 100
- 5 = 101
- 6 = 110
- 7 = 111
각 비트 자리별로 '1'이 설정된 수의 개수를 세면 다음과 같습니다.
- 비트 0: 3, 5, 7 → 3개 (N/2 = 2보다 큼) → X의 비트 0을 1로 설정
- 비트 1: 3, 6, 7 → 3개 (N/2 = 2보다 큼) → X의 비트 1을 1로 설정
- 비트 2: 4, 5, 6, 7 → 4개 (N/2 = 2보다 큼) → X의 비트 2를 1로 설정
따라서 X = 111(2) = 7이 되며, 실제 합계는 (3^7) + (4^7) + (5^7) + (6^7) + (7^7) = 4 + 3 + 2 + 1 + 0 = 10으로 최솟값임을 확인할 수 있습니다.
출력 결과
X = 7, Sum = 10