C++에서 요소 범위 제한 없이 배열의 중복 요소 찾기

N개의 정수로 구성된 배열이 있다고 가정해 보겠습니다. 이 글에서는 주어진 배열 안의 중복 요소를 모두 찾아 출력하는 방법을 다룹니다. 만약 중복된 요소가 하나도 없다면 -1을 반환합니다. 예를 들어 배열이 [12, 15, 12, 3, 6, 12, 3, 48, 56, 8, 48]과 같다면, 중복 요소는 [12, 3, 48]입니다.

접근 방법

이 문제는 C++의 unordered_map(해시 맵)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 배열의 모든 요소를 순회하면서 각 값의 등장 횟수를 unordered_map에 기록합니다. 그런 다음 맵을 다시 순회하면서 등장 횟수가 2 이상인 요소만 골라 출력합니다. 끝까지 탐색했는데도 등장 횟수가 1을 초과하는 요소가 없다면, 중복이 존재하지 않는 것이므로 -1을 출력합니다.

배열 요소의 값 범위에 제한이 없어도 해시 맵은 임의의 정수 키를 저장할 수 있으므로, 값의 크기와 관계없이 동일한 방식으로 적용할 수 있다는 점이 이 방법의 장점입니다.

예제 코드

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

void displayDuplicates(int arr[], int n) {
    unordered_map<int, int> occurrence;

    // 각 요소의 등장 횟수를 카운트
    for (int i = 0; i < n; i++)
        occurrence[arr[i]]++;

    bool duplicate = false;
    unordered_map<int, int>::iterator itr;

    // 등장 횟수가 1보다 큰 요소를 중복으로 판단하여 출력
    for (itr = occurrence.begin(); itr != occurrence.end(); itr++) {
        if (itr->second > 1) {
            cout << itr->first << " ";
            duplicate = true;
        }
    }

    // 중복 요소가 하나도 없으면 -1 출력
    if (!duplicate)
        cout << "-1";
}

int main() {
    int arr[] = {12, 15, 12, 3, 6, 12, 3, 48, 56, 8, 48};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate elements are: ";
    displayDuplicates(arr, n);

    return 0;
}

실행 결과

Duplicate elements are: 12 3 48

복잡도 분석

배열을 한 번 순회하며 카운트를 수행하고(O(n)), 이후 맵을 한 번 더 순회하므로(O(k), k는 서로 다른 요소의 개수) 전체 시간 복잡도는 O(n)입니다. 최악의 경우 모든 요소가 서로 다를 수 있으므로 공간 복잡도 역시 O(n)입니다.

참고로 unordered_map의 평균 삽입·조회 연산은 O(1)이지만, 해시 충돌이 심한 최악의 경우에는 O(n)까지 느려질 수 있습니다. 이를 방지하려면 균형 이진 탐색 트리 기반의 map을 사용할 수도 있으며, 이 경우 시간 복잡도는 O(n log n)이 됩니다.