[프로그래머스] N개의 최소공배수 (JAVA) (level2)

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

프로그래머스

---

문제 설명

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

제한 사항

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

---

※ JAVA 코드 (N개의 최소공배수)

import java.util.*;

class Solution {
    
    static int yaksu;
    
    public static int solution(int[] arr) {
        int answer = 0;
        int num = 1;
        int b = 0;

        int len = arr.length; // 배열크기
        Arrays.sort(arr);

        int tmp = LCM(arr[1], arr[0]);
        int A, B;

        // 최대공약수 반복
        for(int i = 2; i < len; i++) {
            if(arr[i] >= tmp) {
                A = arr[i];
                B = tmp;
            } else {
                A = tmp;
                B = arr[i];
            }

            b = LCM(A, B);
            tmp = b;
        }

        answer = b;

        return answer;
    }

    // 최소공배수
    public static int LCM(int a, int b) {
        return (a * b) / GCD(a, b);
    }

    // 최대공약수
    public static int GCD(int a, int b) {
        // 나누어 떨어지면
        if( a % b == 0) {
            yaksu =  b;
        } else {
            GCD (b, a % b);
        }

        return yaksu;
    }
}

---

※ 생각정리 (N개의 최소공배수)

[알고있어야 하는 상식]

1. 유클리드 호제법 - 두 수의 최대공약수를 구할때 사용하는 알고리즘

두 수 A, B (144, 60)의 최대공약수를 구하기 위해서는 어떤 과정을 거칠까?

먼저, A에서 B를 나눈 나머지를 구한다. 이때 나머지가 0이라면(나누어 떨어진다면) 제수 B가 두수의 최대공약수가 된다.

만약 나머지가 0이 아니라면(나누어 떨어지지 않는다면) 피제수에 B를 제수에 A % B( A를 B로 나눈 나머지)를 대입하여 위의 과정을 반복한다.

이를 코드로 본다면 다음과 같다.

// 최대공약수
public static int GCD(int a, int b) {
    // 나누어 떨어지면
    if( a % b == 0) {
        yaksu =  b;
    } else {
        GCD (b, a % b);
    }

    return yaksu;
}

 

이때, 최대공약수를 활용하여 두 수(A, B)의 최소 공배수까지 구할 수 있다.

최소공배수 = (A * B) / 최대공약수

// 최소공배수
public static int LCM(int a, int b) {
    return (a * b) / GCD(a, b);
}

 

단순히 두수의 최대공약수, 최소공배수를 구하는 문제였다면 해당 문제가 level2이지 않을 것이고 N개의 수(최대 15개)의 수의 최소 공배수를 구하여야한다.

문제해결을 위해 두 수씩 짝지어 최소공배수를 구하여 해당 최소공배수와 다음 수와의 최소공배수를 구하여 순차적으로 문제를 해결하여야한다.

 

- 새벽코딩-