[Algorithm] N개의 최소공배수

 

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

문제 풀이

1. 각 숫자의 소인수들을 구합니다.
2. 소인수들의 최대 개수를 제곱하여 최소공배수를 구합니다.
3. 결과값을 반환합니다.

 

코드 작성

#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int primeSize = sizeof(primes) / sizeof(primes[0]);

unordered_map<int, int> GetPrimeNumCounts(int num)
{
    unordered_map<int, int> map;
    
    while (num != 1)
    {
        for (int i = 0; i < primeSize; ++i)
        {
            if (num % primes[i] == 0)
            {
                map[primes[i]]++;
                num /= primes[i];
            }
        }
    }
    
    return map;
}

int solution(vector<int> arr) {
    unordered_map<int, int> lcmPrimeNumCounts;
    
    for (int num : arr)
    {
       unordered_map<int, int> PrimeNumCounts = GetPrimeNumCounts(num);
       for (auto& pair : PrimeNumCounts)
       {
           if (lcmPrimeNumCounts[pair.first] < pair.second)
           {
               lcmPrimeNumCounts[pair.first] = pair.second;
           }
       }
    }
    
    int answer = 1;
    for (auto& pair : lcmPrimeNumCounts)
    {
        answer *= pow(pair.first, pair.second);
    }    
    
    return answer;
}

 

 

다른 사람 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); }
int lcm(int x, int y) { return x * y / gcd(x, y); }
int solution(vector<int> arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++)
        answer = lcm(answer, arr[i]);
    return answer;
}

• 두 수의 최소 공약수(GCD)를 구한다.
• 두 수의 최대 공배수는 두 수의 곱에서 최소 공약수를 나눈 값이다.
• 결과값인 최대공배수와 다른 수의 최대공배수를 다시 구한다.
• 재귀 함수를 돌렸음에도 큰 수가 아니기에 속도가 빠른 모습을 보여준다.