프로그래머스 lv2 N개의 최소공배수

문제 링크

N개의 최소공배수

풀이

• 숫자 배열을 주고 모든 수의 최소공배수를 구하는 문제이다.
• 최소공배수는 a와 b 두 수가 있다면 (a / 최대공약수) * b 로 구할 수 있다.
• 이 방식을 이용해서 풀이를 해보자.

class Solution {
	public int solution(int[] arr) {
		int lcm = arr[0];

		for (int i = 1; i < arr.length; i++) {
			lcm = (lcm / getGcd(lcm, arr[i])) * arr[i];
		}
		return lcm;
	}

	// 최대공약수를 구하는 메서드
	private int getGcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return getGcd(b, a % b);
	}
}