프로그래머스[Java] - (Level2)N개의 최소공배수

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

프로그래머스

코드

class Solution {
    
    // 최대 공약수
    public int GCD(int a, int b){      
        if(a<b){
            int temp = a;
            a = b;
            b = temp;
        }
        if(b == 0)      return a;
        else            return GCD(b, a%b);
    }
    
    // 최소 공배수 - a*b / 최대공약수
    public int LCM(int a, int b){
        return a*b / GCD(a, b);
    }
    
  public int solution(int[] arr) {
      int answer = arr[0];
      for(int i=1; i<arr.length; i++)
          answer = LCM(answer, arr[i]);
      return answer;
  }
}

풀이

유클리드호제법 을 이용해 최대공약수와 최소공배수를 구하여 풀었다.

N개의 최소공배수는 각각의 최소공배수를 따로 구해주는 것과 동일하다.

A, B, C, D 의 최소공배수는 --> ((A&B)  & C) & D 처럼 두 개씩 최소공배수를 구해주는 것과 같다.

 

최대공약수를 구할때, GCD(int a, int b) 두 매개변수에서 a의값이 b의값보다 커야하므로, GCD 메소드에서

가장 먼저 a의 값과 b의 값을 비교한다.