C/C++로 배열에서 홀수 번 등장하는 숫자를 찾는 방법

이 글에서는 배열 안에서 홀수 번 등장하는 숫자를 찾는 방법을 알아보겠습니다. 이 문제를 해결하는 방법은 여러 가지가 있지만, 그중 가장 간단하고 효율적인 방법 중 하나가 바로 XOR(배타적 OR) 연산을 활용하는 것입니다.

XOR 연산의 원리

XOR 연산에는 다음과 같은 중요한 성질이 있습니다.

• 같은 숫자를 서로 XOR하면 결과는 0이 됩니다. (예: 5 ^ 5 = 0)
• 0과 어떤 숫자를 XOR하면 결과는 그 숫자 자신이 됩니다. (예: 0 ^ 5 = 5)

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

다만 이 방법에는 한 가지 제약이 있습니다. 만약 배열에 홀수 번 등장하는 원소가 두 개 이상 존재한다면, 이 방법으로는 그중 하나만 반환됩니다.

알고리즘

getNumOccurredOdd(arr, n)

begin
    res := 0
    for each element e from arr, do
        res := res XOR e
    done
    return res
end

C++ 구현 예제

#include <iostream>
using namespace std;

int getNumOccurredOdd(int arr[], int n) {
    int res = 0;
    for (int i = 0; i < n; i++)
        res = res ^ arr[i];
    return res;
}

int main() {
    int arr[] = {3, 4, 6, 5, 6, 3, 5, 4, 6, 3, 5, 5, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNumOccurredOdd(arr, n) << " is present odd number of times";
}

실행 결과

6 is present odd number of times

코드 설명

위 예제 배열에서 각 숫자의 등장 횟수를 살펴보면 다음과 같습니다.

• 3 → 4번 (짝수)
• 4 → 2번 (짝수)
• 5 → 4번 (짝수)
• 6 → 3번 (홀수)

모든 요소를 XOR하면 짝수 번 등장한 3, 4, 5는 모두 상쇄되어 사라지고, 홀수 번 등장한 6만 결과로 남게 됩니다.

시간 복잡도

이 방법의 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 배열을 한 번만 순회하면 되고 추가 메모리도 거의 필요하지 않기 때문에 매우 효율적인 해결책이라 할 수 있습니다.