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

🔍 문제

 

---

📊 분석

• 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다는 성질을 가지고 있다.
• 두수의 최소공배수와 최대공배수는 유클리드 호제법을 이용하여 구할수있다.
• 배열의 원소들을 위성질을 이용하여 loop을 하면 최소공배수를 구할수있다.

---

✏️ 풀이

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        
        if(arr.length == 1) return arr[0];
        
        int tmp = gcd(arr[0],arr[1]); // 첫 2개 원소의 최대공약수
        answer = (arr[0]*arr[1]) /tmp;// 첫 2개 원소의 최소공배수
        
         /*  
        원소의 개수가 3개 이상인 경우
        앞의 두 원소의 최소 공배수와 다음 원소의 최소 공배수를 구하며
        배열의 끝까지 반복
        */ 
        if(arr.length >2){
            for(int i = 2; i < arr.length; i++){
                tmp = gcd(answer, arr[i]);
                answer = (answer * arr[i]) / tmp;
            }
        }
        
        return answer;
    }
    
    public static int gcd(int a, int b){
        int r = a % b;
        if(r == 0) return b;
        else return gcd(b, r);
    }
}