[ 프로그래머스 JAVA ] 최소 공배수

문제 출처

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

프로그래머스

걸린 시간

18:20 ~ 18:41 // 소요 시간 21분

피드백

최대 공약수 , 최소 공배수 구하는 알고리즘은 기본으로 외워두자.

문제

두 수의 최소공배수(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

 

수도코드

없음

소스 코드 ( 자세한 내용 주석 참고 )

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        
        int lcm = 0;
        
        for( int i = 1; i < arr.length ; i++ ){
            // 배열 0 , 1 의 최소 공배수 저장 
            if( i == 1 ){
                lcm = LCM(arr[1] , arr[0]);
                continue;
            }
            // 최소 공배수 = ( 직전 최소 공배수 , 새로운 수 ) <- 최소 공배수 
            lcm = LCM( lcm , arr[i] );
        }
        
        answer = lcm;
        return answer;
    }
    
    // 최대 공배수 구하는 함수
    static int GCD ( int M , int N ) {
        if( M % N == 0 ) {
            return N ;
        }
        return GCD( N , M % N );
    }
    
    // 최소 공약수 구하는 함수
    static int LCM ( int M , int N ) {
        return M * N / GCD( M , N );
    }
}