C++로 배열 요소를 가장 많이 나누는 정수 찾기

문제 개요

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 배열의 요소 중 최대한 많은 수를 나눌 수 있는 정수를 찾는 것입니다.

문제 설명: 배열의 요소들을 가장 많이 나눌 수 있는 수 p를 구해야 합니다. 만약 조건을 만족하는 수가 여러 개라면, 그중 더 작은 값을 반환합니다.

예제로 이해하기

• 입력: arr[] = {4, 5, 6, 7, 8}
• 출력: 2
• 설명: 숫자 2는 배열의 {4, 6, 8} 세 요소를 모두 나눌 수 있으므로 정답은 2입니다.

해결 접근 방법

방법 1: 완전 탐색(Brute Force)

가장 단순한 방법은 배열을 순회하면서 각 요소를 1부터 k까지의 수로 나누어 보고, 가장 많은 요소를 나눌 수 있는 수를 반환하는 것입니다. 다만 이 방법은 시간 복잡도가 높아 입력 크기가 클 경우 비효율적입니다.

방법 2: 소인수분해 활용

더 효율적인 접근 방식은 '배열의 모든 요소는 소수 인수들의 곱으로 표현된다'는 수학적 특성을 활용하는 것입니다.

각 소수로 나누어지는 빈도를 저장한 뒤, 빈도가 가장 높은 소수를 답으로 반환하면 됩니다. 소수와 해당 빈도는 해시 맵(map)에 저장하여 관리합니다.

구현 예제 코드

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

#define MAXN 100001
int primes[MAXN];

// 소수 체(Sieve)를 이용해 각 수의 가장 작은 소인수를 미리 계산
void findPrimeSieve()
{
    primes[1] = 1;
    for (int i = 2; i < MAXN; i++)
        primes[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        primes[i] = 2;

    for (int i = 3; i * i < MAXN; i++) {
        if (primes[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (primes[j] == j)
                    primes[j] = i;
        }
    }
}

// num의 서로 다른 소인수 목록을 반환
vector<int> findFactors(int num)
{
    vector<int> factors;
    while (num != 1) {
        int temp = primes[num];
        factors.push_back(temp);
        while (num % temp == 0)
            num = num / temp;
    }
    return factors;
}

int findmaxDivElement(int arr[], int n) {

    findPrimeSieve();
    map<int, int> factorFreq;
    for (int i = 0; i < n; ++i) {

        vector<int> p = findFactors(arr[i]);
        for (int i = 0; i < p.size(); i++)
            factorFreq[p[i]]++;
    }

    int cnt = 0, ans = 1e+7;
    for (auto itr : factorFreq) {
        if (itr.second >= cnt) {
            cnt = itr.second;
            ans > itr.first ? ans = itr.first : ans = ans;
        }
    }

    return ans;
}

int main() {

    int arr[] = { 4, 5, 6, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열의 최대 요소를 나누는 수는 "<<findmaxDivElement(arr, n);
    return 0;
}

실행 결과

배열의 최대 요소를 나누는 수는 2

코드 설명

findPrimeSieve() 함수는 에라토스테네스의 체 원리를 응용하여, 1부터 MAXN까지 각 숫자의 가장 작은 소인수를 미리 계산해 둡니다. 이를 통해 이후 소인수분해를 빠르게 수행할 수 있습니다.

findFactors() 함수는 미리 계산된 소수 체를 참조하여 주어진 수의 서로 다른 소인수들을 추출합니다.

findmaxDivElement() 함수는 배열의 모든 요소를 소인수분해하고, 각 소인수가 등장한 빈도를 맵에 누적합니다. 마지막으로 빈도가 가장 높은 소인수를 결과로 반환합니다. 동일한 빈도를 가진 경우 맵이 오름차순으로 정렬되어 있으므로 자연스럽게 더 작은 값이 유지됩니다.