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

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

프로그래머스

 

class Solution {
    public int solution(int[] arr) {
        int answer = 0;

        if(arr.length == 1) return arr[0]; 

        int g = gcd(arr[0], arr[1]); 
        answer = (arr[0] * arr[1]) / g; 

        if(arr.length > 2) { 
            for(int i = 2; i < arr.length; i++) {
                g = gcd(answer, arr[i]);
                answer = (answer * arr[i]) / g;
            }
        }

        return answer;
    }

    //최대 공약수 구하는 함수
    private static int gcd(int a, int b) {
        int r = a % b;
        if(r == 0) return b;
        else return gcd(b, r);
    }
}

/* 
1. 원소가 한개면 그대로 반환
2. 원소 두 개일 때 최대 공약수와 최소 공배수를 구함
3. 3개 이상일 때 앞의 두 원소의 최소 공배수와 다음 원소의 최소 공배수를 구하며 배열의 끝까지 반복

※두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다는 성질을 가지고 있음
따라서 어떤 두 수의 최대공약수를 구한다면 최소공배수를 쉽게 구할 수 있는데 최대공약수를 구하기 위해 유클리드 호제법을 이용
*/