파이썬으로 정수 배열과 XOR 연산 시 합계를 최소화하는 숫자 X 찾기

문제 개요

정수 배열 A가 주어졌을 때, (A[0] XOR X) + (A[1] XOR X) + … + (A[n−1] XOR X)의 합이 최소가 되도록 하는 수 X를 찾는 것이 이번 포스트의 목표입니다.

예를 들어 입력이 [3, 4, 5, 6, 7]이라면 출력은 X = 7, Sum = 10이 됩니다.

접근 방법: 비트 단위 분석

이 문제를 효율적으로 풀기 위한 핵심 아이디어는 각 비트 위치를 독립적으로 고려하는 것입니다.

XOR 연산에서 특정 비트의 결과는 두 피연산자의 해당 비트가 서로 다를 때만 1이 됩니다. 따라서 어떤 비트 자리에서 배열 원소들의 과반수가 1을 가지고 있다면, X의 그 비트를 1로 설정하는 것이 유리합니다. 그러면 소수의 원소들만 그 비트에서 1을 얻게 되어 전체 합이 줄어들기 때문입니다.

알고리즘 단계

search_res() 함수를 정의합니다. 이 함수는 배열 arr과 배열 크기 n을 매개변수로 받습니다.
배열을 순회하며 최댓값 element를 찾습니다.
비트 길이를 계산합니다: p = int(log2(element)) + 1
X를 0으로 초기화한 뒤, i를 0부터 p까지 반복하며 다음을 수행합니다.
- cnt를 0으로 초기화합니다.
- j를 0부터 n까지 반복하며 arr[j]의 i번째 비트(arr[j] AND 2ⁱ)가 0이 아니면 cnt를 1 증가시킵니다.
- cnt가 n / 2의 정수 부분보다 크면 X에 2ⁱ를 더합니다.
sum을 0으로 초기화하고, 모든 원소에 대해 X XOR arr[i] 값을 누적합니다.
X와 sum을 반환합니다.

파이썬 구현 코드

from math import log2

def search_res(arr, n):
    element = arr[0]
    for i in range(len(arr)):
        if(arr[i] > element):
            element = arr[i]
    p = int(log2(element)) + 1
    X = 0
    for i in range(p):
        cnt = 0
        for j in range(n):
            if (arr[j] & (1 << i)):
                cnt += 1
        if (cnt > int(n / 2)):
            X += 1 << i
    sum = 0
    for i in range(n):
        sum += (X ^ arr[i])
    print("X =", X, ", Sum =", sum)

arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

입력 및 출력 예시

입력:

[3, 4, 5, 6, 7]

출력:

X = 7 , Sum = 10

동작 원리 살펴보기

예시 배열 [3, 4, 5, 6, 7]을 이진수로 표현하면 011, 100, 101, 110, 111입니다.

0번째 비트: 1을 가진 원소가 3개(3, 5, 7)로 과반수 → X의 해당 비트를 1로 설정
1번째 비트: 1을 가진 원소가 3개(3, 6, 7)로 과반수 → X의 해당 비트를 1로 설정
2번째 비트: 1을 가진 원소가 4개(4, 5, 6, 7)로 과반수 → X의 해당 비트를 1로 설정

따라서 X = 111(2진수) = 7이 되며, 각 원소와의 XOR 합은 (7^3)+(7^4)+(7^5)+(7^6)+(7^7) = 4+3+2+1+0 = 10입니다.

시간 복잡도

최댓값 탐색에 O(n), 비트별 카운팅에 O(p × n)(p는 최댓값의 비트 수), 합계 계산에 O(n)이 소요되므로, 전체 시간 복잡도는 O(p × n)입니다. 일반적인 정수 범위에서 p는 상수로 취급할 수 있어 사실상 선형 시간에 해결됩니다.