[프로그래머스] Lv.2 : N개의 최소공배수 - 자바[Java]

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

프로그래머스

 

풀이

앞에서부터 두 수의 최소공배수를 구하고, 구한 최소공배수와 배열의 다음 수의 최소공배수를 또 구하고, 이런 과정을 반복해서 최종적으로 모든 수의 최소공배수를 구하면 된다.

로직

1. a, b, gcd, lcm 변수를 선언한다.

2. a와 lcm은 arr[0]으로 초기화한다. arr은 길이가 1이상인 배열이기 때문에 첫번째 원소가 바로 정답이 될 수 있기 때문이다.

3. for문에서 다음과 같은 과정을 반복한다.

• b에 arr[1]을 할당한다.
• a와 b의 최대공약수를 GCD 메서드를 통해 구하고, 최대공약수를 통해 최소공배수를 구해 lcm에 저장한다.
• a에 lcm을 할당한다. 

4. 최종적으로 모든 수들의 최소공배수를 반환한다.

 

코드

class Solution {
    public int solution(int[] arr) {
        int a, b, gcd, lcm;
        a = lcm = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            b = arr[i];
            gcd = GCD(a, b);
            lcm = a * b / gcd;
            
            a = lcm;
        }
        return lcm;
    }
    
    public int GCD(int a, int b) {
        if (a == 0)
            return b;
        
        return GCD(b % a, a);
    }
}