[프로그래머스] N개의 최소공배수 (Java/자바) - 유클리드호제법

문제

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

프로그래머스

 

문제 풀이

유클리드 호제법을 이용하여 순서대로 arr[i-1]과 arr[i]의 최소공배수를 구하기

arr[i-1]와 arr[i]의 최소 공배수를 arr[i]에 갱신

 

유클리드 호제법

2개 숫자의 최대 공약수를 구하는 알고리즘

자연수 a와 b에 대해 a를 b로 나눈 나머지 r이라고 하면,

a와 b의 최대 공약수와 b와 r의 최대공약수는 같다.

a를 b로 나눈 나머지 r을 구한 뒤, b를 r로 나눈 나머지 r2를 구함

나머지가 0이 될 때, 나눈 수가 a와 b의 최대 공약수가 됨.

 

코드

    public static int getGCD(int a, int b){
        if(a%b==0){
            return b;
        }
        return getGCD(b, a%b);
    }

 

이 때, a와 b의 최소공배수는 a * b / (최대공약수)

 

 

전체 코드

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        
        for(int i=1; i<arr.length; i++){
            int gcd = getGCD(arr[i-1], arr[i]);
            arr[i] = arr[i-1] * arr[i] / gcd;
        }
        answer = arr[arr.length-1];
        return answer;
    }
    
    public static int getGCD(int a, int b){
        if(a%b==0){
            return b;
        }
        return getGCD(b, a%b);
    }
}