[프로그래머스] N개의 최소공배수

문제 설명

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

제한사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

---

풀이

10분
배열을 순회하며 소인수분해를 하고, 그 결과값들을 통해서 최소공배수를 구했다. 상당히 비효율적인 코드지만, 원소의 크기와 배열 길이를 고려했을 때 가능할 것 같아 그대로 풀었다. 그리고나서 예전에 최소공배수, 최대공약수를 구하는 깔끔한 코드를 배운 기억이 어렴풋이 있어서 찾아 공부했다.
찾다가 ‘유클리드 호제법’이라는 단어를 보자마자, 작년 정보보호 수업 때 직접 손으로 계산했던 기억들이 스쳐지나갔다. 이걸 벌써 까먹다니…

코드

// 03:57 ~ 04:07

#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <iostream>

using namespace std;

int solution(vector<int> arr) {
    int total[101];
    int soinsu[101];
    int res = 1;
    
    memset(total, 0, sizeof(total));
    for(int n : arr){
        memset(soinsu, 0, sizeof(soinsu));
        int i = 2;
        while(n > 1){
            if(n % i == 0){
                soinsu[i]++;
                n /= i;
            }
            else
                ++i;
        }
        
        for(int i = 2; i < 100; ++i){
            if(soinsu[i] > total[i]) total[i] = soinsu[i];
        }
    }
    for(int i = 2; i < 100; ++i){
        if(total[i] > 0){
            res *= pow(i,total[i]);
        }
    }
    return res;
}

유클리드 호제법

// 03:57 ~ 04:07

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> arr) {
    int res = arr[0];
    int a, b, r;
    for(int i = 1; i < arr.size(); ++i){
        // get gcd
        a = max(res,arr[i]);
        b = min(res,arr[i]);
        while((r = a % b) != 0){
            a = b;
            b = r;
        }
        
        //get lcm(lcm = a*b/gcd(a,b))
        res = res * arr[i] / b;
    }
    return res;
}