C++로 배열에서 특정 숫자의 빈도(등장 횟수) 구하기

배열에 n개의 서로 다른 요소가 저장되어 있다고 가정해 보겠습니다. 이때 배열 안에서 특정 요소가 몇 번 등장하는지, 즉 빈도(frequency)를 확인해야 하는 경우가 있습니다.

예를 들어 A = [5, 12, 26, 5, 3, 4, 15, 5, 8, 4]라는 배열에서 숫자 5의 빈도를 구하면 3이 됩니다.

해결 방법

이 문제는 매우 간단한 선형 탐색(linear search) 기법으로 해결할 수 있습니다.

배열의 왼쪽(첫 번째 요소)부터 차례대로 탐색하면서, 현재 요소가 찾고자 하는 숫자와 같으면 카운터를 1 증가시키고, 같지 않다면 아무 작업 없이 다음 요소로 넘어갑니다. 이 과정을 배열의 마지막 요소까지 반복하면, 최종적으로 카운터에 해당 숫자의 빈도가 저장됩니다.

예제 코드

#include<iostream>
using namespace std;

int countElementInArr(int arr[], int n, int e) {
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] == e)
            count++;
    }
    return count;
}

int main() {
    int arr[] = {5, 12, 26, 5, 3, 4, 15, 5, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int e = 5;
    cout << "Frequency of " << e << " in the array is: "
         << countElementInArr(arr, n, e);
}

실행 결과

Frequency of 5 in the array is: 3

코드 설명

• countElementInArr 함수는 배열과 배열의 크기(n), 그리고 찾고자 하는 값(e)을 매개변수로 받습니다.
• for 루프를 통해 배열 전체를 한 번씩 순회하며, 조건문(arr[i] == e)이 참일 때마다 카운터를 증가시킵니다.
• sizeof(arr)/sizeof(arr[0])를 사용하면 배열의 크기를 하드코딩하지 않고 자동으로 계산할 수 있습니다.

이 방법의 시간 복잡도는 O(n)으로, 배열의 모든 요소를 한 번씩 확인해야 하므로 배열의 크기에 비례하여 탐색 시간이 늘어납니다. 배열이 정렬되어 있지 않은 경우에는 이 방법이 가장 일반적이고 효율적인 접근 방식입니다.