LV2 N개의 최소공배수 (Java)

 

---

 

문제

 

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

프로그래머스

 

풀이

나무위키로 최소 공배수의 특징을 확인하였다.

 

 

세개 이상의 수의 최소 공배수를 구하기 위해서는, 두 수의 최소공배수와 새로운 수의 최소 공배수를 구하면 된다. 

 

두 수의 최소 공배수 같은 경우에는 최대 공약수(gcd)를 통해서 구할 수 있는데, 

 

최대공약수는 유명한 "유클리드 호제법" 으로 구할 수 있다.

 

따라서, 두 수의 최대 공약수를 구한 후에 이 값을 활용하여 최대 공배수를 구하는 과정을 반복적으로 수행하면 풀이할 수 있다.

 

코드

import java.util.*;

// lcm(a,b,c)=lcm(lcm(a,b),c)
class Solution {
    
    // (a > b)
    public int lcm(int a, int b){
        
        int absVal = Math.abs(a) * Math.abs(b);
        
        if(b > a){
            int temp = a;
            a = b;
            b = temp;
        }
        
        while(b != 0){
            int r = a%b;
            a = b;
            b = r;
        }
        
        return absVal/a;
    }
    
    public int solution(int[] arr) {
        
        int first = arr[0];
        
        if(arr.length == 1){
            return arr[0];
        }
        
        for(int i=1; i<arr.length; i++){
            int second = arr[i];
            first = lcm(first, second);
        }
        
        return first;
    }
}

 

후기