Hayden's Archive
[알고리즘] 프로그래머스 : N개의 최소공배수 본문
알고리즘 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12953
관련 포스팅 : https://hayden-archive.tistory.com/140
내가 작성한 코드
- 먼저 유클리드 호제법을 활용해서 재귀함수를 써서 최소공배수를 리턴하는 메소드를 작성한다.
- 아이디어 : "세 수의 최소공배수"는 "두 수의 최소공배수"와 "다른 한 수"의 최소공배수와 같다.
① 두 수의 최대공약수를 구한다. ② 최대공약수를 바탕으로 3가지 경우(서로소인 경우/작은 수가 큰 수의 최대공약수인 경우/그 외 두 수의 최대공약수가 존재하는 경우)로 나누고, 경우에 맞게 최소공배수를 구한다. ③ 그 최소공배수와 다음 수의 최대공약수를 구한다. ->반복...
class Solution {
public int solution(int[] arr) {
int lcm = arr[0];
for(int i=0; i<arr.length; i++) {
int gcd = gcd(lcm, arr[i]);
if(gcd == 1) lcm = lcm * arr[i];
else if(Math.min(lcm, arr[i]) == gcd) lcm = Math.max(lcm, arr[i]);
else lcm = gcd * (lcm/gcd) * (arr[i]/gcd);
}
return lcm;
}
public int gcd(int a, int b) {
if(b==0) return a;
return gcd(b, a%b);
}
}