[Programmers/JAVA] N개의 최소공배수 / 프로그래머스 코딩 테스트 연습

N개의 최소공배수

---

문제 설명

 

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

---

예시

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

---

코드 해석 및 전체 코드

 

1. [0]과 [1]의 최소 공배수 L 구하기

2. L과 [2 + n]의 최소 공배수 구하기

 

예시 1의 배열은 2, 6, 8, 14로 총 4가지의 숫자로 구성되어 있다. 

먼저 배열의 인덱스 0, 1의 최소공배수를 구한다. 최소 공배수를 구하기 위해 유클리드 호제법을 사용했다. 

그리고 for문을 인덱스 2부터 시작해 배열의 길이만큼 반복한다. (0, 1의 최소 공배수와 2의 최소 공배수를 구하기 위해)

for문이 종료된 뒤의 최소 공배수가 배열에 담긴 수들의 최소 공배수가 된다. 

 

두 수(최초 2, 6 | 이후 lcm, i)	최대 공약수	최소 공배수
2, 6	2	6
6, 8	2	24
24, 14	2	168

 

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        int gcd = GCD(arr[0], arr[1]); // [0], [1]의 최대 공약수 구하기
        int lcm = arr[0] * arr[1] / gcd; // [0], [1]의 최소 공배수 구하기
        
        //위에서 구한 최소 공배수와 [2]의 최대 공약수, 최소 공배수 구하기
        //최소공배수와 [i]의 최대 공약수와 최소 공배수를 배열이 끝날 때까지 반복한다. 
        // 마지막으로 구해진 최소 공배수가 배열 모든 수의 최소 공배수이다.
        for(int i = 2; i < arr.length; i++){
            gcd = GCD(lcm, arr[i]);
            lcm = lcm * arr[i] / gcd;
        }
        answer = lcm;
        return answer;
    }
    
    // 최대공약수를 반환하는 함수
    private int GCD(int a, int b){
        if( a % b == 0) return b;
        return GCD(b, a % b);
    }
}

---

유클리드 호제법

2개의 수의 최대 공약수를 구하는 알고리즘

 

a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구함

나머지가 0이 될 때까지 나눈 수가 최대 공약수의 수

 

코드는 위의 최대공약수를 구하는 코드

---

github

programmers