[프로그래머스] N개의 최소공배수 문제

Lv2문제, 자바로 풀이했습니다.

---

<문제 설명>

두 수의 최소공배수(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

---

<내 풀이>

입력의 첫번째 값을 기준으로 다음 값과의 최소공배수를 구하고,

구해진 최소공배수와 입력의 다음 값의 최소공배수를 구하고,,

이렇게 반복되며 입력의 끝까지 최소공배수를 반복해 구한다.

 

최소공배수는 두 수의 곱을 최대 공약수로 나눈 값이다.

최대공약수를 구하기 위해서 유클리드호제법을 활용했다.

class Solution {
  public int solution(int[] arr) {
		int lcm = arr[0];
		for(int i=1; i<arr.length; i++) {
			lcm = getLcm(lcm, arr[i]);
		}
		return lcm;
	}
	
	public int getGcd(int a, int b) {
		int tmp;
		while(b != 0) {
			tmp = b;
			b = a % b;
			a = tmp;
		}
		return a;
	}
	
	public int getLcm(int a, int b) {
		if(a<=0 || b<=0) return -1;
		return a * b / getGcd(a, b);
	}
}

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스

---

유클리드호제법에 대한 풀이는 알고리즘 이론으로 정리해서 올리겠습니다.