프로그래머스 | LV.2 N개의 최소 공배수 - 유클리드 호제법 (Java)

⬛ 프로그래머스 | LV.2 N개의 최소 공배수 - 유클리드 호제법

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

프로그래머스

문제 설명

---

💚나의 풀이

• 이 문제를 풀기 위해서는 ‘유클리드 호제법’에 대해서 알아야 한다.
• 1) 최대 공약수를 구할 때, ‘유클리드 호제법’을 사용하여 구하고
• 2) 최소 공배수 = (a * b) / 최대 공약수 로 구한다.
• 따라서 이 문제는 유클리드 호제법을 먼저 이해하는 게 중요하다.

[풀이 설명]

• gcd(int a, int b) 함수는 유클리드 호제법을 활용한 최대공약수 구하는 함수이다.
• 1) 큰수 % 작은 수 mod 연산
• 2) 앞 단계에서의 작은 수 % 그 결과 나머지 mod 연산
• 3) 나머지가 0이 되면 그때의 작은 수를 최대공약수로 선택함

💚 제출 코드

/*
1) 유클리드 호제법으로 '최대 공약수 ' 구하기
2) 최대 공배구 = a * b / 최대 공약수 
*/

import java.util.*;
class Solution {
    static int gcd(int a, int b){
       int r = a%b;
       if(r == 0) return b;
       else return gcd(b, r);
    }
    
    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;
    }
}