C++로 주어진 XOR 값을 만족하는 쌍의 개수 구하기

이 튜토리얼에서는 주어진 XOR 값과 일치하는 쌍(pair)의 개수를 구하는 프로그램을 다룹니다.

배열과 하나의 목표 값이 주어지며, 우리의 과제는 두 원소의 XOR 연산 결과가 해당 값과 같아지는 쌍이 배열 안에 몇 개 있는지 찾는 것입니다.

접근 방식

모든 쌍을 하나씩 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸리기 때문에 비효율적입니다. 대신 해시 맵(unordered_map)을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• 배열을 순회하면서 각 원소 arr[i]에 대해, 이 원소와 XOR했을 때 목표 값 x가 되는 수는 x ^ arr[i]입니다.
• 그 값이 이미 맵에 등장한 적이 있다면, 그 등장 횟수만큼 결과에 더해줍니다.
• 이후 현재 원소의 빈도를 맵에 기록합니다.

맵에 빈도를 저장하기 때문에 중복된 값이 있어도 자연스럽게 처리됩니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;

// XOR이 주어진 값과 같은 쌍의 개수를 반환
int count_pair(int arr[], int n, int x){
    int result = 0;
    // 중복 값 처리를 위한 빈도 맵
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++){
        int curr_xor = x ^ arr[i];
        if (m.find(curr_xor) != m.end())
            result += m[curr_xor];
        m[arr[i]]++;
    }
    return result;
}

int main(){
    int arr[] = {2, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 0;
    cout << "Count of pairs with given XOR = " << count_pair(arr, n, x);
    return 0;
}

출력

Count of pairs with given XOR = 1

동작 과정 살펴보기

예제 배열 {2, 5, 2}와 목표 값 x = 0으로 단계별로 확인해 보겠습니다.

1. i = 0: curr_xor = 0 ^ 2 = 2 → 맵에 없으므로 넘어감, m[2] = 1
2. i = 1: curr_xor = 0 ^ 5 = 5 → 맵에 없으므로 넘어감, m[5] = 1
3. i = 2: curr_xor = 0 ^ 2 = 2 → 맵에 존재(빈도 1), result += 1 → result = 1

즉, 2 ^ 2 = 0을 만족하는 쌍 (arr[0], arr[2]) 하나가 정답이 됩니다.

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회하고, 해시 맵의 탐색과 삽입은 평균 O(1)입니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 원소를 맵에 저장해야 합니다.