C++로 배열에서 XOR 값이 0이 되는 쌍의 개수 구하기

n개의 요소로 이루어진 배열이 주어졌을 때, XOR 연산의 결과가 0이 되는 쌍(pair)의 개수를 구하는 문제입니다.

XOR의 성질을 생각해 보면, 쌍 (x, y)의 XOR 결과가 0이 되려면 x와 y가 반드시 같은 값이어야 합니다. 예를 들어 5 ⊕ 5 = 0이지만, 서로 다른 두 수의 XOR이 0이 되는 경우는 없습니다. 따라서 이 문제는 결국 “배열에서 값이 서로 같은 두 요소로 몇 개의 쌍을 만들 수 있는가?”를 묻는 것과 같습니다.

접근 방법

가장 효율적인 해결 방법은 배열을 먼저 정렬하는 것입니다. 정렬을 하면 같은 값들이 인접한 위치에 모이게 되므로, 앞에서부터 인접한 두 요소를 비교하면서 값이 같으면 카운트를 1씩 증가시키면 됩니다.

단, 모든 요소가 동일한 경우에는 마지막 쌍이 누락될 수 있습니다. 이를 보완하기 위해 배열의 첫 번째 요소와 마지막 요소가 같은지 한 번 더 확인하고, 같다면 카운트를 1 증가시킨 뒤 결과를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

int countPairs(int arr[], int n) {
    int count = 0;
    sort(arr, arr + n);
    for(int i = 0; i < n - 1; i++) {
        if(arr[i] == arr[i+1]) {
            count++;
        }
    }
    if(arr[0] == arr[n-1])
        count++;
    return count;
}

int main() {
    int arr[] = {1, 2, 1, 2, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of pairs: " << countPairs(arr, n);
}

실행 결과

Number of pairs: 2

동작 원리 살펴보기

예제 배열 {1, 2, 1, 2, 4}를 정렬하면 {1, 1, 2, 2, 4}가 됩니다. 인접한 요소를 차례로 비교하면 (1, 1)과 (2, 2)에서 값이 일치하므로 카운트는 2가 됩니다. 첫 번째 요소(1)와 마지막 요소(4)는 서로 다르므로 추가 증가는 없으며, 최종 결과는 2입니다.

이 알고리즘의 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 이중 반복문으로 모든 쌍을 하나씩 확인하는 브루트 포스 방식(O(n²))보다 훨씬 효율적이라는 장점이 있습니다.