링크

문제링크

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력

arr	result
[2,6,8,14]	168
[1,2,3]	6

해결

여러개의 최소공배수는 2개의 최소공배수를 구하고 그 최소공배수와 다음 숫자의 최소공배수를 구해 반복하면 N개 숫자의 최소공배수가 된다.

[2,3,8,5] 의 최소 공배수 일경우

• 2 , 3의 최소공배수 6
• 6, 8의 최소공배수 24
• 24, 5의 최소공배수 120 으로 구해진다.

유클리드 호제법을 사용하여 getGCD() 를 구현한다.
a > b 일때 a는 b의 값을 가지고 a % b 값은 다음 b의값이 된다.
이렇게 b가0이될때까지 반복하면 a의값은 최대공약수가 남는다.

최소공배수는 두 수의 곱 / 두 수의 최대공약수 이다.

코드

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        
        int lcm = arr[0];
        
        // N개의 수의 최소공배수 구하기
        for (int i = 0; i < arr.length - 1; i++) {
            int a = lcm;

            lcm = a * arr[i + 1] / getGCD(a, arr[i + 1]);
        }
        
        answer = lcm;
        
        return answer;
    }
    
    private static int getGCD(int a, int b) {
        int c;

        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }

        while (b > 0) {
            c = a % b;
            a = b;
            b = c;
        }

        return a;
    }
}