[java] level2 / 연습문제 / 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

---

[풀이]

두 수의 최소공배수를 계산하여 비교

import java.util.Arrays;

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

        Arrays.sort(arr);
		
		for (int i = 1; i < arr.length; i++) {
			if(answer < arr[i]) {
				max = arr[i];
				min = answer;
			} else {
				max = arr[i];
				min = answer;
			}
			answer = max*min/gcd(max, min);
		}
        
        return answer;
    }
    
    public static int gcd(int a, int b) { //최대공약수.
        if(a%b ==0) {
            return b;
        } else {
            return gcd(b, a%b);
        }
    }
}

1) for문을 돌며 배열 두칸의 숫자의 최소 공배수를 구함.

1-1)첫번째는 arr[0] 번째 수를 담고,

1-2) i번째와 i+1 번째를 비교하여 더 큰 숫자와 그 다음 배열의 값을 비교.

 

2) 두 수의 최대공약수를 구해서 최소공배수를 구함.

2-1) gcd() 함수는 두 수의 최대공약수를 구하는 함수.

2-2) max*min/gcd(max, min); 공식을 이용하여 두 수의 최대공배수를 구함.

 

3) 마지막에 구한 최소공배수를 반환