C++에서 섞인 배열에서 누락된 숫자 찾기 – XOR 트릭 완벽 가이드

두 개의 배열 A와 B가 있다고 가정해 보겠습니다. 배열 A는 n개의 요소를 가지고 있으며, 두 번째 배열 B는 A의 모든 요소를 포함하지만 순서가 섞여(shuffled) 있고 그중 하나의 요소가 제거되어 있습니다. 우리의 목표는 이 누락된 요소를 찾아내는 것입니다.

예를 들어 A = [4, 8, 1, 3, 7]이고 B = [7, 4, 3, 1]이라면, B에는 없는 요소인 8이 출력되어야 합니다.

XOR 연산을 활용한 해결 원리

이 문제는 XOR(배타적 논리합) 트릭을 사용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 누락된 요소를 제외한 나머지 모든 요소는 배열 A와 B에 각각 한 번씩, 즉 총 두 번 등장합니다.
• 누락된 요소는 오직 배열 A에만 한 번 등장합니다.
• XOR의 성질상 x XOR x = 0이며, 어떤 값에 0을 XOR해도 자기 자신이 유지됩니다(x XOR 0 = x).

따라서 두 배열의 모든 요소를 차례대로 XOR 연산하면, 두 번 등장한 요소들은 모두 0으로 상쇄되고 최종적으로 한 번만 등장한 누락된 숫자만 결과로 남게 됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int FindMissingElement(int A[], int B[], int n) {
    int missing = 0;
    // 배열 A의 모든 요소를 XOR 연산
    for (int i = 0; i < n; i++)
        missing = missing ^ A[i];
    // 배열 B의 모든 요소를 XOR 연산
    for (int i = 0; i < n - 1; i++)
        missing = missing ^ B[i];
    return missing;
}

int main() {
    int A[] = {4, 8, 1, 3, 7};
    int B[] = {7, 4, 3, 1};
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Missing element: " << FindMissingElement(A, B, n);
}

실행 결과

Missing element: 8

시간 및 공간 복잡도

이 알고리즘은 두 배열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.

정렬(O(n log n))이나 해시 맵(O(n)이지만 추가 메모리 필요)을 사용하는 방식과 비교했을 때, XOR 트릭은 속도와 메모리 측면 모두에서 가장 효율적인 접근 방법이라 할 수 있습니다.