C++로 약수 배열에서 원래 숫자 찾기

이 문제에서는 어떤 수 Num의 약수들로 이루어진 N개의 정수 배열 divisors[]가 주어집니다. 우리가 해야 할 일은 이 약수 배열만 보고 원래의 수 Num을 찾아내는 것입니다.

단, 약수 배열에는 1과 그 수 자신은 포함되지 않는다는 점에 유의해야 합니다.

문제 이해를 위한 예시

입력

divisors[] = {3, 25, 5, 15}

출력

75

설명

숫자 75의 약수는 {3, 25, 5, 15}이며, 주어진 배열과 정확히 일치하므로 정답은 75입니다.

해결 접근 방법

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다. 어떤 수의 약수 중 가장 작은 약수와 가장 큰 약수를 곱하면 그 수 자신이 됩니다.

Num = 최소 약수 × 최대 약수

따라서 다음 단계로 진행할 수 있습니다.

1. 배열 divisors[]를 오름차순으로 정렬합니다.
2. 첫 번째 요소(최소 약수)와 마지막 요소(최대 약수)의 곱을 계산하여 후보 수 Num을 구합니다.
3. Num의 실제 약수들을 모두 구합니다.
4. 구한 약수들이 주어진 약수 배열과 완전히 일치하는지 확인합니다.

일치한다면 Num을 반환하고, 일치하지 않거나 약수의 개수가 다르다면 해당 약수 집합을 만족하는 수가 존재하지 않는다는 의미로 -1을 반환합니다.

솔루션 구현 예제

#include <bits/stdc++.h>
using namespace std;
int findNumberFromDiv(int divisors[], int n){
    sort(divisors, divisors + n);
    int num = divisors[0] * divisors[n - 1];
    int numDiv[2*n];
    int count = 0;
    for (int i = 2; i * i <= num; i++){
        if (num % i == 0){
            numDiv[count] = i;
            count++;
            numDiv[count] = num/i;
            count++;
        }
    }
    sort(numDiv, numDiv + count);
    if (count != n)
        return -1;
    else{
        for (int i = 0; i < count; i++) {
            if (divisors[i] != numDiv[i])
                return -1;
        }
    }
    return num;
}
int main(){
    int divisors[] = { 3, 25, 5, 15 };
    int n = sizeof(divisors) / sizeof(divisors[0]);
    cout<<"The number is "<<findNumberFromDiv(divisors,n);
    return 0;
}

실행 결과

The number is 75

코드 설명

위 코드는 먼저 약수 배열을 정렬한 뒤, 최소 약수와 최대 약수의 곱으로 후보 수를 구합니다. 이후 √num까지만 반복하면서 짝을 이루는 약수(i와 num/i)를 모두 수집하고, 개수와 각 값을 주어진 배열과 비교하여 유효성을 검증합니다. 시간 복잡도는 정렬과 약수 탐색을 포함하여 대략 O(N log N + √Num)입니다.