프로그래머스 코딩테스트 - N개의 최소공배수

문제 설명

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

 

 

 

 

내가 푼 문제 풀이

최대공약수 또는 최소공배수를 구할 때 유클리드 알고리즘(호제법)을 자주 쓴다.

나도 유클리드 호제법을 사용해서 문제를 풀어봤다.

 

자세한 내용은 아래 참고!

유클리드 호제법(Euclidean algorithm)

 

 

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
        int val = arr[0];
        int sum = 1;
        
        for(int i=0; i<arr.length-1; i++){
            int mul = arr[i+1] * val; // 두 수의 곱
            
            if(arr[i+1] > val){       // 큰수 / 작은수를 하기 위해 구분
                val = gcd(arr[i+1], val);
            }else { 
                val = gcd(val, arr[i+1]); 
            }
            
            val = mul / val;			// 두 수의 곱 / 최대공약수
        }
        
        return val;
    }
    
    public int gcd(int a,int b){
        return a % b == 0 ? b : gcd(b, a%b);
    }
}

 

 

두 수 a와 b (a>b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

이 과정을 반복하여 나머지가0이 될 때 나누는 수가 두 수의 최대공약수이다. 

 

a x b를 두 수의 최대공약수로 나누면 그 값이 최소공배수이다.

 

그래서 나는 arr [2,6,8,14] 테스트 케이스를 기준으로,

2와 6의 최소공배수를 구하고, 그 값과 8의 최소공배수, 그 값과 14의 최소공배수

이런식으로 순차적으로 구했다.