C++에서 배열의 최솟값 빈도를 찾는 방법

이 글에서는 배열에서 가장 작은 요소가 몇 번 나타나는지, 즉 최솟값의 빈도를 구하는 방법을 알아보겠습니다.

예를 들어 배열이 [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10]이라고 가정해 봅시다. 이 배열에서 가장 작은 값은 3이며, 이 값은 총 4번 등장합니다. 따라서 프로그램의 출력 결과는 4가 됩니다.

문제 해결 접근 방식

이 문제는 두 단계로 간단하게 해결할 수 있습니다.

1. 먼저 배열을 한 번 순회하며 최솟값을 찾습니다.
2. 다시 배열을 순회하면서 해당 최솟값과 일치하는 요소의 개수를 세어 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

// 배열에서 최솟값을 찾는 함수
int min_element(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min)
            min = arr[i];
    }
    return min;
}

// 최솟값의 빈도를 계산하는 함수
int smallestNumFreq(int *arr, int n) {
    int minimum = min_element(arr, n);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == minimum)
            count++;
    }
    return count;
}

int main() {
    int arr[] = {5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Frequency of smallest element: " << smallestNumFreq(arr, n);
}

실행 결과

Frequency of smallest element: 4

코드 설명

min_element() 함수는 배열의 첫 번째 요소를 초기 최솟값으로 설정한 뒤, 나머지 요소들을 차례대로 비교하며 더 작은 값이 있으면 갱신합니다. 시간 복잡도는 O(n)입니다.

smallestNumFreq() 함수는 앞서 구한 최솟값을 기준으로 배열 전체를 탐색하며 동일한 값의 개수를 카운트합니다. 이 역시 O(n)의 시간 복잡도를 가지므로, 전체 알고리즘의 시간 복잡도는 O(n)입니다.

만약 두 번의 순회를 피하고 싶다면, 단일 순회 과정에서 현재까지의 최솟값과 그 빈도를 함께 추적하는 방법으로도 문제를 해결할 수 있습니다. 새로운 최솟값이 발견되면 빈도를 1로 초기화하고, 같은 값이 나오면 빈도를 증가시키면 됩니다.