JAVA 알고리즘 - N개의 최소공배수 구하기

문제 설명

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

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.

arr의 원소는 100 이하인 자연수입니다.

문제풀이

공약수란 두 수의 또는 여러 수의 공통인 약수 라는 뜻이다.

최대공약수란?

- 가장 큰 공약수

- 공약수이자, 모든 공약수의 배수인 양의 정수

- 재귀적 정의는 gcd ( gcd ( gcd(n1, n2), n3 ), n4 ) ...

그냥,,,, gcd(n1, n2) 로 암기하자.

최소공배수란?

두 수의 또는 공통되는 두 수의 배수 라는 뜻입니다.

최소공배수를 구하는 방법은 공약수로 나누어서 곱하는 방법이 있습니다.

lcm = a*b / 최대공약수;

package com.education.solution.chap01;
import java.util.Arrays;
/**
 * N개의 최소공배수 구하기
 * @author user
 *
 */
public class LcmGcd {
	public static void main(String[] args) {
		int[] arr = {2, 6, 8, 14};
		int answer = 0;
		Arrays.parallelSort(arr);
		int tmp = arr[0];		
		for ( int i=0; i<arr.length; i++ ) {
			tmp = lcm(tmp, arr[i]);
		}
		answer = tmp;
		System.out.println(answer);
		
	}
	
	/**
	 * 최소공배수 구하기
	 * 알고리즘 문제에서 가장 많이 쓰이는 식인데
	 * 최소공배수 = 두수의 곱 / 두수의 최대공약수
	 */
	static int lcm( int a, int b ) {
		return a*b / gcd(a, b);
	}
	
	
	/**
	 * 최대공약수 구하기
	 * a%b = b가 0이 아닐때까지 나눠서 a를 리턴한다.
	 * 두수가 있으면 처음에 그 중 한 수(여기서는 b)로 나누고 나머지를 임시 변수(c)에 저장하고 나누어진수(a)는 나눈수(b)가 되고 나눈수(b)는 임시변수(r)이 된다. 
	 * 그리고 b가 0이 아닐때 까지 반복하다 0이 되면 a를 return 하게 되는데 a가 a,b의 최대공약수가 된다.
	 */
	static int gcd( int a, int b ) {
		
		while (b!=0) {
			int c = a%b;
			a=b;
			b=c;
		}
		
		return a;
	}
	
}