C++로 배열에서 한 번만 나타나는 요소 찾기 – XOR 활용법

배열 A가 주어졌다고 가정해 봅시다. 이 배열에는 대부분의 숫자가 정확히 두 번씩 등장하지만, 딱 하나의 숫자만 한 번 등장합니다. 우리의 목표는 바로 이 유일한 요소를 찾아내는 것입니다.

예를 들어 A = [1, 1, 5, 3, 2, 5, 2]라면 출력은 3이 되어야 합니다. 다른 숫자들은 모두 두 번씩 나타나지만 3만 한 번 등장하기 때문입니다.

XOR 연산의 핵심 원리

이 문제는 XOR(배타적 논리합) 연산을 활용하면 매우 우아하게 해결할 수 있습니다. XOR에는 다음과 같은 중요한 성질이 있습니다.

• 같은 수를 XOR하면 0이 됩니다. 즉, y XOR y = 0
• 0과 어떤 수를 XOR하면 그 수 자신이 됩니다. 즉, 0 XOR y = y
• XOR은 교환 법칙과 결합 법칙이 성립하므로 연산 순서와 무관하게 결과가 같습니다.

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

해결 절차

• 결괏값을 저장할 변수 res를 0으로 초기화합니다.
• 배열 A의 각 요소 e에 대해 res := res XOR e를 수행합니다.
• 모든 반복이 끝난 후 res를 반환합니다. 이 값이 곧 정답입니다.

C++ 구현 예제

다음 구현을 통해 더 쉽게 이해할 수 있습니다.

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

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            ans ^= nums[i];
        }
        return ans;
    }
};

int main() {
    Solution ob1;
    vector<int> arr = {1, 1, 5, 3, 2, 5, 2};
    cout << ob1.singleNumber(arr) << endl;
    return 0;
}

입력

[1, 1, 5, 3, 2, 5, 2]

출력

3

복잡도 분석

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 없이 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다. 해시 맵이나 정렬을 사용하는 방법보다 훨씬 효율적인 접근 방식입니다.