배열이 주어졌을 때, 그중 가장 자주 등장하는 요소(최빈값)를 찾아야 하는 문제는 코딩 테스트와 실무에서 자주 만나게 되는 기본적인 알고리즘 문제입니다. 먼저 간단한 예시를 통해 문제를 이해해 보겠습니다.
문제 예시
입력
arr = [1, 2, 3, 3, 2, 2, 1, 1, 2, 3, 4]
출력
2
위 배열에서 숫자 2는 총 4번 등장하며, 다른 어떤 요소보다도 많이 나타납니다. 따라서 정답은 2입니다.
알고리즘 1 — 해시 맵(Map) 활용
배열을 초기화합니다.
각 요소의 빈도를 저장할 맵(unordered_map)을 준비합니다.
배열을 한 번 순회하면서 각 요소의 등장 횟수를 세어 맵에 저장합니다.
맵을 순회하며 빈도가 가장 높은 요소를 찾습니다.
해당 요소를 반환합니다.
이 방법의 시간 복잡도는 O(n)으로, 배열을 정렬할 필요 없이 선형 시간에 해결할 수 있어 효율적입니다.
알고리즘 2 — 정렬(Sort) 활용
배열을 초기화합니다.
주어진 배열을 오름차순으로 정렬합니다.
최대 등장 횟수(max count), 결과값(result), 현재 요소의 연속 횟수(current count)를 저장할 변수를 준비합니다.
정렬된 배열을 순회하며 가장 많이 등장한 요소를 찾습니다.
정렬 후에는 동일한 요소들이 서로 인접해 있으므로, 연속된 구간의 길이만 비교하면 됩니다.
결과를 반환합니다.
이 방법은 정렬 과정이 포함되므로 시간 복잡도는 O(n log n)입니다.
C++ 구현 코드
다음은 위에서 설명한 알고리즘 1(해시 맵 방식)을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int getMostFrequentNumber(int arr[], int n) {
unordered_map<int, int> elements;
for (int i = 0; i < n; i++) {
elements[arr[i]]++;
}
int maxCount = 0, res = -1;
for (auto i : elements) {
if (maxCount < i.second) {
res = i.first;
maxCount = i.second;
}
}
return res;
}
int main() {
int arr[] = { 1, 2, 3, 3, 2, 2, 1, 1, 2, 3, 4 };
int n = 11;
cout << getMostFrequentNumber(arr, n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 확인할 수 있습니다.
2
마무리
배열의 최빈값을 구하는 문제는 해시 맵을 이용한 빈도 계산이 가장 일반적이고 효율적인 접근 방식입니다. 데이터의 범위가 작다면 카운팅 배열(counting array)을 사용할 수도 있고, 메모리 사용을 줄여야 한다면 정렬 기반 방식도 좋은 대안이 됩니다. 문제의 조건에 맞게 적절한 방법을 선택해 활용해 보세요.