정수로 이루어진 배열 A가 있고 그 크기가 n이라고 가정해 봅시다. 우리의 목표는 O(n)보다 적은 시간 안에 배열에 포함된 모든 요소의 빈도(출현 횟수)를 구하는 것입니다. 단, 요소들의 값은 특정 값 M 이하로 제한되어 있다는 전제 조건이 붙습니다.
이 문제는 일반적인 해시맵이나 선형 순회 방식으로도 풀 수 있지만, 배열이 이미 정렬되어 있다면 더 효율적인 방법을 사용할 수 있습니다. 핵심 아이디어는 이진 탐색(binary search)에서 착안한 분할 정복(divide and conquer) 기법입니다.
알고리즘 접근 방식
배열이 오름차순으로 정렬되어 있다는 점을 활용하면 다음과 같이 동작합니다.
- 탐색 구간의 양 끝 요소가 서로 다르면, 해당 구간을 반으로 나누어 각각 재귀적으로 처리합니다.
- 양 끝 요소가 서로 같다면, 배열이 이미 정렬되어 있으므로 그 구간 내의 모든 요소가 동일하다는 의미입니다. 따라서 해당 값의 빈도에 구간 길이(right - left + 1)를 한 번에 더해 주면 됩니다.
이렇게 하면 각각의 고유한(distinct) 값마다 재귀 트리에서 최대 O(log n)개의 노드만 방문하게 되므로, 고유한 값의 개수를 k라고 할 때 전체 시간 복잡도는 O(k · log n)이 됩니다. k가 n보다 작은 경우, 즉 중복이 많은 배열에서는 O(n)보다 빠른 성능을 얻을 수 있습니다.
C++ 구현 예제
#include<iostream>
#include<vector>
using namespace std;
void calculateFreq(int arr[], int left, int right, vector<int>& frequency) {
// 구간의 양 끝 값이 같으면 그 구간 전체가 동일한 값
if (arr[left] == arr[right])
frequency[arr[left]] += right - left + 1;
else {
// 값이 다르면 구간을 반으로 나누어 재귀 호출
int mid = (left + right) / 2;
calculateFreq(arr, left, mid, frequency);
calculateFreq(arr, mid + 1, right, frequency);
}
}
void getAllFrequency(int arr[], int n) {
// 최댓값(arr[n-1]) 크기만큼의 빈도 배열 생성
vector<int> frequency(arr[n - 1] + 1, 0);
calculateFreq(arr, 0, n - 1, frequency);
// 빈도가 0이 아닌 요소만 출력
for (int i = 0; i <= arr[n - 1]; i++)
if (frequency[i] != 0)
cout << "Frequency of element " << i << " is " << frequency[i] << endl;
}
int main() {
int arr[] = { 10, 10, 10, 20, 30, 30, 50, 50, 80, 80, 80, 90, 90, 99 };
int n = sizeof(arr) / sizeof(arr[0]);
getAllFrequency(arr, n);
}실행 결과
Frequency of element 10 is 3 Frequency of element 20 is 1 Frequency of element 30 is 2 Frequency of element 50 is 2 Frequency of element 80 is 3 Frequency of element 90 is 2 Frequency of element 99 is 1
코드 설명
- calculateFreq 함수: 현재 구간 [left, right]의 양 끝 값을 비교합니다. 두 값이 같으면 구간 전체가 하나의 값으로 채워져 있으므로 빈도 배열에 구간 길이를 바로 누적하고, 다르면 mid를 기준으로 두 구간으로 나누어 재귀 호출합니다.
- getAllFrequency 함수: 배열의 최댓값(arr[n-1])을 기준으로 빈도를 저장할 vector를 0으로 초기화한 뒤, 재귀 함수를 호출하고 마지막에 빈도가 0이 아닌 요소들만 출력합니다.
마무리
이 기법은 정렬된 배열에서 중복된 값이 많을 때 특히 유용합니다. 해시 기반 counting(O(n)) 대신 분할 정복을 사용하면 고유 값의 개수가 적은 경우 O(n)보다 적은 시간에 모든 요소의 빈도를 계산할 수 있습니다. 다만 배열이 정렬되어 있지 않다면 먼저 정렬(O(n log n))이 필요하므로, 입력 조건을 반드시 확인해야 합니다.