[프로그래머스/C++]Lv.2 - N개의 최소공배수

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953

내 풀이

재귀를 이용한 유클리드 호재법을 사용하였다.
반복문으로 2개씩 묶어가면서 두 개의 최대공약수를 구해서 최소공배수를 구하고 i+1에 대입해준다. 끝까지 반복하면 마지막은 모든 수의 최소공배수가 나온다.
오름차순으로 정렬한 이유는 작은수부터 해나가야 할 것같아서 했다. 속도적인 측면도 더 좋을 것 같았다.

내 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int Euclidean(int a,int b)
{
    return b ? Euclidean(b , a % b) : a;
}
int solution(vector<int> arr) {
    int answer = 1;
    sort(arr.begin(),arr.end());
    for(int i = 0; i < arr.size() - 1; i++)
    {
        int a = Euclidean(arr[i], arr[i + 1]);
        arr[i+1] = arr[i] * arr[i+1] / a;
    }
    answer = arr.back();
    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;
}

다른 사람의 풀이 해석

이론은 같지만 좀 더 깔끔하다. 똑같이 유클리드 호재법으로 최대공약수를 구하고 최소공배수를 구하는 것도 함수화 하였다. answer에 arr[0]을 미리 대입 해두고
answer을 갱신해나가는 방법을 사용하였다.
굳이 정렬해두지 않아도 될 것 같다.