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

 

문제

프로그래머스

 

알고리즘

유클리드 호제법

 

풀이

[2, 6, 8, 14] 가 있다면

2와 6의 최소공배수 = 6,

6와 8의 최소공배수 = 24

24와 14의 최소공배수 = 168 이 된다.

즉 모든 수에 대해 현재까지 구한 최소공배수와 다음 수의 최소공배수를 구해 현재까지 구한 최소공배수를 갱신하면 된다.

 

a 와 b의 최소공배수는 a * b / (a와 b의 최대공약수) 로 구할 수 있고,

a 와 b의 최대공약수는 유클리드 호제법을 이용하여 구할 수 있다.

 

 

코드

class Solution {
	public int solution(int[] arr) {
		int num = 1;

		for (int i = 0; i < arr.length; i++)
			num = (num * arr[i]) / getGcd(num, arr[i]);

		return num;
	}

	public int getGcd(int a, int b) {
		if (b > a) {
			int tmp = a;
			a = b;
			b = tmp;
		}

		while (a % b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}

		return b;
	}
}