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

양의 정수로 이루어진 배열에서 홀수 번 등장하는 수를 찾는 C++ 프로그램을 살펴보겠습니다. 이 배열에서는 모든 수가 짝수 번씩 등장하고, 단 하나의 수만 홀수 번 나타난다고 가정합니다.

입력: arr[] = {5, 7, 8, 8, 5, 8, 8, 7, 7}
출력: 7

위 예제에서 각 요소의 등장 횟수를 세어 보면 다음과 같습니다.

5 → 2번 (짝수)
7 → 3번 (홀수) ✅
8 → 4번 (짝수)

알고리즘 설명

가장 직관적인 방법은 중첩 반복문(이중 루프)을 사용하는 것입니다.

외부 루프는 배열의 모든 요소를 하나씩 순회합니다.
내부 루프는 외부 루프가 현재 가리키는 요소와 같은 값을 가진 요소의 개수(등장 횟수)를 셉니다.
등장 횟수를 2로 나눈 나머지가 0이 아니면(즉, 홀수 번 등장하면) 해당 요소를 반환합니다.

모든 요소를 확인한 후에도 조건에 맞는 값이 없다면 -1을 반환하여 그런 수가 없음을 알립니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int Odd(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int ctr = 0;
        // 현재 요소 arr[i]의 등장 횟수 계산
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                ctr++;
        }
        // 홀수 번 등장하는 경우 해당 값 반환
        if (ctr % 2 != 0)
            return arr[i];
    }
    return -1; // 홀수 번 등장하는 수가 없는 경우
}

int main() {
    int arr[] = {5, 7, 8, 8, 5, 8, 8, 7, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << Odd(arr, n);  // 출력: 7
    return 0;
}

실행 결과

시간 복잡도 분석

위 방법은 이중 루프를 사용하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 커질수록 실행 속도가 크게 느려질 수 있습니다.

더 효율적인 방법: XOR 연산 활용

배열에 홀수 번 등장하는 수가 정확히 하나뿐이라면, XOR(Exclusive OR) 비트 연산을 이용해 O(n) 시간에 해결할 수 있습니다. XOR은 같은 수를 두 번 연산하면 0이 되는 성질을 가지므로, 짝수 번 등장하는 수는 모두 상쇄되고 홀수 번 등장하는 수만 남습니다.

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {5, 7, 8, 8, 5, 8, 8, 7, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << OddXOR(arr, n);  // 출력: 7
    return 0;
}

이 방법은 추가 메모리 없이 한 번의 루프만으로 답을 찾을 수 있어, 실무에서도 널리 사용되는 최적화 기법입니다.

정리

이중 루프 방식: 이해하기 쉽지만 O(n²)의 시간 복잡도를 가집니다.
XOR 방식: O(n)으로 빠르며, 단 하나의 수만 홀수 번 등장할 때 적용 가능합니다.