[프로그래머스,Level 2] N개의 최소공배수 (JAVA 구현)

- 첫 풀이 및 정답풀이

  이 문제를 접하자마자 최소공배수, 최대공약수가 나오는 문제는 유클리드 호제법 알고리즘을 이용해야 한다는 사실을 알고 있었기 때문에 접근 자체는 쉬울 것이라 생각했다. 그러나, 앞서 level 1인 최소공배수, 최대공약수 문제에서는 2개의 자연수에 대해서만 적용해 보았기 때문에 N 개는 어떻게 접근해야 할지 몰랐다.

 

  N개의 최소공배수뿐 아니라 최대공약수 역시 앞서 두 개의 자연수에 대해 해당 값들을 구한 뒤, 해당 값들과 다음 값의 최대공약수, 최소공배수를 구하면 N개에 대해 구할 수 있다는 사실을 알 수 있었다. 

 

  예제 입력1을 예로 들면, 처음 두 수인 2와 6에 대해서 유클리드 호제법 알고리즘을 이용해 최대공약수 2와 최소공배수 6을 구할 수 있다. 여기서 구한 최소공배수 6과 다음 8의 최대공약수 2와 최소공배수 24를 구한다. 이를 반복하면 문제가 원하는 결과를 반환할 수 있다.

class Solution {
    
    // 5. 최대공약수 메소드, 유클리드 호제법
    public static int gcd(int a, int b){
        int x = Math.max(a,b);
        int y = Math.min(a,b);
        
        while(x % y != 0){
            int r = x % y;
            x = y;
            y = r;
        }
        
        return y;
    }
    
    public int solution(int[] arr) {
        // 1. 배열의 첫 번째 값을 저장.
        int answer = arr[0];
        
        // 2. 배열의 길이가 1이면 반복x, 그 이상은 다음 인덱스인 1부터 반복.
        for(int i = 1;i<arr.length;i++){
            // 3. 두 값의 최대공약수
            int gcd = gcd(answer,arr[i]);
            // 4. 두 값의 최소공배수
            answer = answer * arr[i] / gcd;
        }
        
        return answer;
    }
}