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

---

풀이과정

• 최소공배수 구하기
  a * b = (a,b의 최소공배수) * (a,b의 최대공약수) 공식을 활용해 구합니다.
  
  
• 최대공약수 구하기
  유클리드 호제법을 이용해 a%b가 0이 될 때까지 재귀함수를 호출하고 나눠떨어질 때의 b값이 최대공약수가 됩니다.

위의 최소공배수와 최대공약수를 구하는 방법을 활용해 다음과 같은 순서로 풀어내었습니다.

 

1.  arr배열에 들어있는 0번 수와 1번 수의 최소공배수를 구합니다.
2. 1에서 구한 최소공배수와 다음 숫자인 arr[2]의 최소공배수를 구합니다.
3. ....arr[arr.length-1]까지의 최소공배수를 구해 해당 값을 return 합니다.

---

전체 코드

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for(int i=0;i<arr.length;i++){
            answer=lcm(answer,arr[i]);
        }
        
        return answer;
    }
    //최소공배수 Least Common Multiple
    int lcm(int a, int b){
        return a*b /gcd(a,b);
    }
    //최대공약수 Greatest Common Divisor
    int gcd(int a, int b){
        //유클리드 호제법
        if(a%b==0)
            return b;
        
        return gcd(b,a%b);
    }
}