배열에서 두 번 이상 나타나는 요소 찾는 방법

이번 글에서는 배열 관련 문제 하나를 살펴보겠습니다. 주어진 배열에서 빈도가 2회 이상인 요소를 모두 찾아 출력하는 것이 과제입니다.

예를 들어 배열이 {1, 5, 2, 5, 3, 1, 5, 2, 7}이라고 가정해 봅시다. 이 배열에서 1은 2번, 5는 3번, 2는 3번 등장하고, 나머지 요소(3, 7)는 각각 1번만 나타납니다. 따라서 결과로 출력되어야 할 값은 {1, 5, 2}입니다.

알고리즘

moreFreq(arr, n)

Begin
    key와 value가 모두 int 타입인 map을 정의한다
    arr의 각 요소 e에 대해 다음을 수행한다
        map.key(arr)의 value를 증가시킨다
    done
    각 key의 value가 1보다 큰지 확인하고, 그렇다면 해당 key를 출력한다
End

예제 코드

아래 C++ 코드는 해시 맵(map)을 활용해 각 요소의 등장 횟수를 세고, 빈도가 1을 초과하는 요소만 골라 출력합니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.

#include <iostream>
#include <map>
using namespace std;
void moreFreq(int arr[], int n){
    map<int, int> freq_map;
    for(int i = 0; i<n; i++){
        freq_map[arr[i]]++; // 빈도 증가
    }
    for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
        if (it->second > 1)
            cout << it->first << " ";
    }
}
int main() {
    int arr[] = {1, 5, 2, 5, 3, 1, 5, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Frequency more than one: ";
    moreFreq(arr, n);
}

실행 결과

Frequency more than one: 1 2 5

출력 결과를 보면 1, 2, 5가 두 번 이상 등장한 요소임을 확인할 수 있습니다. 이처럼 map 자료구조를 사용하면 중복 요소의 빈도를 손쉽게 계산할 수 있으며, 배열의 크기가 커져도 선형 시간 안에 문제를 해결할 수 있습니다.