[ 나의 풀이 ]
#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
int solution(vector<int> arr) {
int answer = 1;
map<int,int> m;
for(int i=0;i<arr.size();i++)
{
map <int,int> temp;
int n = arr[i];
int j=2;
while(n != 1)
{
if(n % j == 0){
temp[j]++;
n = n/j;
}else{
j++;
}
}
for(auto it = temp.begin();it != temp.end();it++)
{
int idx = it->first;
int value = it->second;
m[idx] = max(m[idx], value);
}
}
for(auto it = m.begin();it != m.end();it++){
answer *= pow(it->first,it->second);
}
return answer;
}
- 모든 수를 대상으로 최소 공배수를 구하려면 각 약수들의 최대 차수들의 곱이 필요하다고 생각했음
- 그래서 모든 수의 약수를 구했고, 최대 값들만 map에 저장하여 계산했음
- 밑에 풀이가 더 간단하고 똑똑한 풀이!
[ 최적 코드 ]
#include <string>
#include <vector>
using namespace std;
int GCD(int a, int b){
if(a == 0) return b;
return GCD(b%a,a);
}
int LCM(int a, int b){
return a*b / GCD(a,b);
}
int solution(vector<int> arr) {
int answer = 0;
answer = arr[0];
for(int i=1;i<arr.size();i++){
answer = LCM(answer, arr[i]);
}
return answer;
}
- key point!
: 앞에 2개씩 차례차례 최소 공배수를 구하면 결국 모든 수의 최소공배수를 구할 수 있음
- 최대공약수를 구하는 GCD와 최소공배수를 구하는 LCM을 만드는 함수는 외워두자!
- 이것은
유클리드 호제법
을 재귀
로 구현한 것이다