C++로 배열에서 반복되는 요소 찾기: map을 활용한 빈도수 계산 방법

개요

이 튜토리얼에서는 주어진 배열에서 두 번 이상 등장하는 요소(반복 요소)를 찾는 C++ 프로그램을 작성해 보겠습니다. 각 요소의 등장 횟수를 저장하기 위해 map(맵) 자료구조를 활용하며, 가장 먼저 발견된 중복 요소를 반환하는 방식으로 문제를 해결합니다.

문제 해결 접근 방법

문제를 해결하는 과정은 다음과 같습니다.

배열을 초기화합니다.
배열에 포함된 각 요소의 빈도수를 저장할 카운터 맵을 선언합니다.
배열을 순회하면서 각 요소가 이미 맵에 존재하는지 확인합니다.
- 존재한다면 해당 요소의 빈도수를 1 증가시킵니다.
- 존재하지 않는다면 새로운 항목으로 삽입합니다.
빈도수가 1보다 큰 첫 번째 요소를 찾아 반환합니다.

예제 코드

전체 코드는 다음과 같습니다.

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

int findRepeatingElement(int arr[], int n) {
    map<int, int> frequencies;
    for (int i = 0; i < n; i++) {
        map<int, int>::iterator itr = frequencies.find(arr[i]);
        if (itr != frequencies.end()) {
            itr->second = itr->second + 1;
        }
        else {
            frequencies.insert({arr[i], 1});
        }
    }
    for (map<int, int>::iterator itr = frequencies.begin(); itr != frequencies.end(); ++itr) {
        if (itr->second > 1) {
            return itr->first;
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 3, 4, 5, 5, 6};
    cout << findRepeatingElement(arr, 8) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

배열 {1, 2, 3, 3, 4, 5, 5, 6}에서 값 3이 가장 먼저 두 번 등장했기 때문에 3이 출력됩니다.

시간 및 공간 복잡도 분석

시간 복잡도: O(n log n) — 각 요소를 맵에 삽입 또는 조회하는 데 O(log n)이 소요되며, 총 n개의 요소를 처리합니다.
공간 복잡도: O(n) — 최악의 경우 모든 요소가 서로 다를 때 맵에 n개의 항목이 저장됩니다.

만약 정렬 여부와 상관없이 더 빠른 성능이 필요하다면, unordered_map을 사용하여 평균 O(n)의 시간 복잡도로 개선할 수 있습니다.

마무리

이번 튜토리얼에서는 C++의 map 자료구조를 사용하여 배열에서 반복되는 요소를 찾는 방법을 알아보았습니다. 코드 실행 중 궁금한 점이 있다면 댓글로 남겨주세요.