[프로그래머스] (Lv.2) N개의 최소공배수 **

문제

---

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

 

-  출력 예시  -

정답 코드

---

<  내 정답 코드  >

class Solution {
    public int solution(int[] arr) {
        
        int max = Math.max(arr[0], arr[1]);
        int min = Math.min(arr[0], arr[1]);
        
        int GCD = gcd(max, min);
        int LCM = (arr[0] * arr[1]) / GCD;
        
        for (int i = 2; i < arr.length; i++) {
            LCM = (LCM * arr[i]) / gcd(Math.max(LCM, arr[i]), Math.min(LCM, arr[i]));
        }
        
        return LCM;
    }
    
    public static int gcd(int max, int min) {  
        if (max % min == 0) {
            return min;
        }
        
        return gcd(min, max % min);
    }
}

 

<  타인 답변 코드  >

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

이것을 주의하자!

---

-  '최대공약수(GCD)' 와 '최소공배수(LCM)' 관련된 문제다. '최소공배수(LCM)' 를 구하려면 먼저 '최대공약수(GCD)'를 얻어야 한다.

 

최대공약수(GCD)   =   '유클리드 호제법'  :  큰 수를 작은 수로 나눠서 나머지가 0 이 될 때 나눈 수

최소공배수(LCM)  =  a   *   b   /   GCD

 

-  만약 여러 숫자가 있으면 차례대로 계산해야 한다. [  A  ,  B  ,  C  ,  D  ,  E  ]  가 있다면 먼저 A 와 B 의 최소공배수(LCM)를 구하고, 이를 C 와의 최소공배수를 구한다. 그리고 나온 값을 D 와의 최소공배수를 구한다. 그리고 나온 값을 E 와의 최소공배수를 구하면 된다.

 

-  내 정답 코드는 좀 지저분하다. 반면 타인 답변 코드는 비교적 깔끔하다. 어짜피 앞에서 계산된 최소공배수가 다시 매개변수로 사용될 것이기에 하나로 통일했다.