C++로 정수 배열에서 가장 많이 등장하는 요소 찾는 방법

크기가 N인 정수 배열이 주어졌을 때, 배열 안에서 가장 자주 등장하는 요소(최빈값)를 찾아야 하는 문제입니다. 예제를 통해 살펴보겠습니다.

입력-1 −

N = 8
A[ ] = {1,2,4,3,3,1,1,5}

출력 −

1

설명 − 주어진 정수 배열에서 가장 많이 등장하는 숫자는 '1'입니다. 따라서 출력 결과는 '1'이 됩니다.

입력-2 −

N = 6
A[ ] = {1,4,4,4,1,1}

출력-a −

1

출력-b −

4

설명: 이 배열에서는 '1'과 '4'가 각각 3번씩 등장하여 최빈값이 두 개입니다. 이 경우 둘 중 어느 하나를 출력해도 정답으로 인정됩니다.

문제 해결 접근 방법

주어진 배열에는 여러 개의 정수가 포함되어 있으며, 그중 가장 빈도가 높은 요소를 찾아야 합니다. 시간 복잡도 O(n)과 공간 복잡도 O(n)의 선형 시간 안에 이 문제를 해결하려면 해시맵(hashmap)을 활용하는 방법이 효과적입니다.

이 접근 방식에서는 키(key)-값(value) 쌍으로 구성된 unordered map(C++ STL 라이브러리)을 생성합니다. 여기서 키는 배열의 요소가 되고, 값은 해당 요소의 등장 횟수가 됩니다. 맵을 순회하면서 등장 횟수가 가장 큰 숫자를 찾아 결과로 반환합니다.

• 크기 N의 정수 배열을 입력받습니다.

• 정수형 함수 maxOccurrence(int A[], int size)는 배열과 배열의 크기를 입력으로 받아 최대 빈도를 가진 숫자를 반환합니다.

• 배열의 모든 요소에 대해 해시맵을 생성합니다. 이때 키는 요소 값, 값은 해당 요소의 빈도수가 됩니다.

• 맵을 순회하면서 가장 높은 빈도를 가진 요소가 있는지 확인하고, 있다면 해당 숫자를 결과로 반환합니다. 만약 배열에 어떤 숫자도 존재하지 않는다면 '-1'을 반환합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
    int mxcount=0;
    int res=-1;
    unordered_map<int,int>mp;
    for(int i=0;i<size;i++){
        mp[A[i]]++;
    }
    for(auto x:mp){
        if(x.second>mxcount){
            res= x.first;
            mxcount=x.second;
        }
    }
    return res;
}
int main(){
    int N=6;
    int A[N]= {1,4,4,4,2,1};
    int ans= maxOccurrence(A,N);
    cout<<ans<<endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

4

숫자 '4'는 3번 등장했으며, 이는 주어진 배열의 다른 모든 숫자들보다 높은 최대 빈도입니다. 따라서 프로그램은 '4'를 최빈값으로 출력합니다.