[Java/자바] 프로그래머스 Lv2 - N개의 최소공배수 (유클리드 호재법)

문제 설명

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

 

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

---

Solution.java

이 문제를 풀기위해선 유클리드 호재법을 사용합니다.

저번 Lv1 문제를 풀면서 유클리드 호재법을 정리해놓은 글이 있으니 참고하시면 좋습니다.

[알고리즘] 유클리드 호제법 - 최소공배수, 최대공약수 구하기

 

위 유클리드 호재법은 두 수의 최소 공배수와 최대 공약수를 구하는 방식이고

이 문제 처럼 두 개 이상의 수의 최소 공배수를 구하는 방식은 조금 다릅니다.

먼저 코드를 보고 설명하겠습니다.

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];

        for (int i = 1; i < arr.length; i++) {
                answer = lcm(answer, arr[i]);
        }
        return answer;
    }

    // 최대공약수
    private static int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }

    // 최소공배수
    private static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

문제 풀이

arr의 값이 {2, 6, 8, 14}라고 가정하고 설명하겠습니다.

1. N개의 수의 최소공배수를 구하므로 기존의 두 수의 최대공약수, 최소공배수를 구하는 방식과 다르게 answer의 값을 arr의 첫 번째 값으로 고정합니다.
2. 1번째 인덱스 값과 2번째 인덱스 값의 최소공배수를 answer에 반영하고 그 최소공배수와 다음 3번째 인덱스와의 최소공배수를 구합니다.
3. 1, 2번째 인덱스의 최소공배수 값과 3번째 인덱스 두 수의 최소공배수를 구한 값을 answer에 반영합니다.
4. 이와 같은 방법으로 마지막 인덱스의 값과도 최소공배수를 구해 answer에 반영합니다.

값의 최소공배수는 다음과 같이 비교하면서 N개의 최소공배수를 구합니다.

| 현재 a 값 : 2 |  현재 b 값 : 6 | a, b의 최소공배수 : 6 |
| 현재 a 값 : 6 |  현재 b 값 : 8 | a, b의 최소공배수 : 24 |
| 현재 a 값 : 24 |  현재 b 값 : 14 | a, b의 최소공배수 : 168 |