C++에서 가장 많은 배열 요소로 나누어 떨어지는 숫자 찾기

소개

이 튜토리얼에서는 주어진 배열에서 가장 많은 배열 요소로 나누어 떨어지는 숫자를 찾는 방법을 알아봅니다. 즉, 배열 내 요소들에 의해 가장 많이 나누어지는 요소가 몇 개의 요소로 나누어지는지 그 최대 개수를 구하는 것입니다.

문제를 해결하는 단계는 다음과 같습니다.

• 배열과 결과값을 저장할 변수를 초기화합니다.
• 배열을 순회합니다.
  • 카운터 변수를 초기화합니다.
  • 배열을 다시 한 번 순회합니다.
    • 현재 요소가 해당 배열 요소로 나누어 떨어지면 카운터를 1 증가시킵니다.
  • 현재 카운트가 지금까지의 최댓값보다 크면 결과를 갱신합니다.
• 최종 결과를 출력합니다.

예제 코드

전체 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int numberWithMaximumMultiples(int arr[], int n) {
    int result = -1;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] % arr[j] == 0) {
                count++;
            }
        }
        if (count > result) {
            result = count;
        }
    }
    return result;
}

int main() {
    int arr[] = {4, 24, 16, 3, 12, 28};
    cout << numberWithMaximumMultiples(arr, 6) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

4

동작 원리

예제 배열 {4, 24, 16, 3, 12, 28}에서 각 요소를 자기 자신을 포함한 배열 내 요소들로 나누어 보면, 24는 4, 3, 12, 24 총 4개의 요소로 나누어 떨어집니다. 이것이 배열 전체에서 가장 많은 개수이므로 프로그램은 4를 반환합니다.

이 알고리즘은 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n²)입니다. 따라서 배열의 크기가 매우 큰 경우에는 성능에 유의해야 합니다.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.