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을 갱신해나가는 방법을 사용하였다.
굳이 정렬해두지 않아도 될 것 같다.