C++로 정렬된 배열에서 특정 요소의 등장 횟수(빈도) 구하기

정수형 요소로 이루어진 정렬된 배열과 하나의 숫자 num이 주어졌을 때, 해당 요소가 배열 안에 몇 번 등장하는지 그 횟수(빈도)를 계산하는 것이 이번 글의 목표입니다.

예시

입력 − int arr[] = {1, 1, 1, 2, 3, 4}, num = 1
출력 − 정렬된 배열에서의 등장 횟수(빈도)는 − 3

입력 − int arr[] = {2, 3, 4, 5, 5, 6, -7}, num = 5
출력 − 정렬된 배열에서의 등장 횟수(빈도)는 − 2

입력 − int arr[] = {-1, 0, 1, 2, 3}, num = 7
출력 − 정렬된 배열에서의 등장 횟수(빈도)는 − 0

해결 접근 방법

위 문제를 해결하기 위한 방법은 여러 가지가 있으며, 대표적으로 두 가지 접근법을 소개합니다.

1. 단순 탐색(Naive Approach)

양수와 음수를 모두 포함하는 정수형 배열과, 빈도를 찾아야 할 정수 변수 num을 선언합니다.
배열의 크기를 계산한 뒤, 모든 데이터를 처리용 함수에 전달합니다.
num이 등장하는 횟수를 저장할 임시 변수 count를 선언합니다.
i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
루프 내부에서 num == arr[i]인지 확인하고, 참이라면 count 값을 1 증가시킵니다.
반복이 끝나면 count를 반환합니다.
결과를 출력합니다.

이 방식은 배열 전체를 한 번씩 확인하므로 시간 복잡도는 O(n)입니다.

2. 효율적 탐색(Efficient Approach)

배열이 이미 정렬되어 있다는 점을 활용하면 더 빠르게 해결할 수 있습니다. C++ STL의 lower_bound와 upper_bound 함수를 사용하면 이분 탐색 기반으로 O(log n)의 시간 복잡도에 해결할 수 있습니다.

양수와 음수를 모두 포함하는 정수형 배열과, 빈도를 찾아야 할 정수 변수 num을 선언합니다.
배열의 크기를 계산한 뒤, 모든 데이터를 처리용 함수에 전달합니다.
num이 등장하는 횟수를 저장할 임시 변수 count를 선언합니다.
first 포인터를 lower_bound(arr, arr+size, num)로 설정합니다. 이는 num 이상의 값이 처음 나타나는 위치를 가리킵니다.
first == (arr + size) 또는 *first != num이라면 해당 요소가 배열에 없으므로 0을 반환합니다.
last 포인터를 upper_bound(first, arr+size, num)로 설정합니다. 이는 num보다 큰 값이 처음 나타나는 위치를 가리킵니다.
count = last - first로 두 포인터 사이의 거리를 계산합니다.
count를 반환하고 결과를 출력합니다.

예제 코드 (단순 탐색)

#include <iostream>
using namespace std;
int frequency_count(int arr[], int num, int size){
    int count = 0;
    for(int i=0; i<size; i++){
        if(num==arr[i]){
            count++;
        }
    }
    return count;
}
int main(){
    int arr[] = {1, 1, 1, 2, 3, 4};
    int num = 1;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"정렬된 배열에서의 등장 횟수(빈도): "<<frequency_count(arr, num, size);
    return 0;
}

실행 결과

정렬된 배열에서의 등장 횟수(빈도): 3

예제 코드 (효율적 탐색)

# include <bits/stdc++.h>
using namespace std;
int frequency_count(int arr[], int num, int size){
    int *first = lower_bound(arr, arr+size, num);
    if (first == (arr + size) || *first != num){
        cout<<"해당 요소는 배열에 존재하지 않습니다.";
        return 0;
    }
    int count = 0;
    int *last = upper_bound(first, arr+size, num);
    count = last - first;
    return count;
}
int main(){
    int arr[] = {1, 1, 1, 2, 3, 4};
    int num = 1;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"정렬된 배열에서의 등장 횟수(빈도): "<<frequency_count(arr, num, size);
    return 0;
}

실행 결과

정렬된 배열에서의 등장 횟수(빈도): 3

마무리

배열이 정렬되어 있지 않다면 단순 탐색(O(n)) 외에 선택지가 없지만, 정렬된 배열이라면 lower_bound와 upper_bound를 조합한 이분 탐색 방식(O(log n))이 훨씬 효율적입니다. 데이터 크기가 클수록 두 방식의 성능 차이는 더욱 커지므로, 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.