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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

2. 입력

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

3. 예제

arr	result
[2,6,8,14]	168
[1,2,3]	6

4. 풀이

이 문제를 풀기에 앞서 두 수의 최대 공약수를 구하는 알고리즘인 유클리드 호제법에 대해서 간단하게 설명을 하고자 합니다.

• 유클리드 호제법 이란
  2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘을 말한다.
• 유클리드 호제법 공식
  A, B 두수는 자연수이고 a가 b보다 커야 된다. 즉(A > B)
  2개의 자연수 A, B에 대해서 A를 B로 나눈 나머지를 R이라 하면 A와 B의 최대 공약수는 B와 R의 최대공약수와 같게 된다. 그러므로 B를 R로 나눈 나머지 R1을 구한 뒤 다시 R을 R1으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대 공약수다.
  

이제 최대 공약수를 구했으니 두수의 최소 공배수를 구해보도록 하겠습니다.

 

두 수의 최소 공배수는 두수 A와 B를 곱한 값에서 방금 위에서 구한 최대 공약수로 나누면 됩니다. 즉(A*B / 최대 공약수)

 

지금까지는 두 수에 대한 최소 공배수를 구했으므로 문제 해결을 위한 두 수가 아닌 여러 수에 대한 최대 최소 공배수는 어떻게 구하는지만 해결하면 이번 문제는 해결이 될  것 입니다.

 

수가 여러개 인 경우 먼저 앞 두 수에 대한 최소 공배수를 구한 뒤 구해진 최소 공배수와 다음 수 1개와 최소 공배수를 구하면 3개의 수에 대한 최소 공배수를 구할 수 있습니다.

 

그렇다면 많은 수의 최소 공배수는 먼저 가장 앞의 두 수에 대한 최소 공배수를 구한뒤 구해진 공배수와 다음 수에 대한 최소 공배수를 구하고 또 구해진 최소 공배수와 다음 수의 최소 공배수를 구하는 작업을 반복하면 됩니다.

 

코드를 보면 GCD함수가 유클리드 호제법을 구현 한 것 입니다.

 

먼저 A와 B를 비교하여 큰 수가 A위치에 올 수 있도록 하고 유클리드 호제법 처럼 나머지가 0이 될 때까지 A % B를 한 값 R을 다시 B % R을 반복하도록 되어 있습니다.

 

이제 최대 공약수를 구하는 함수는 구현이 되었으므로 최소 공배수를 구하는 (이전 최소 공배수 * 다음 수 / GCD(이전 최소 공배수, 다음 수)) 작업을 반복하면 입력으로 주어진 수의 최소 공배수를 구할 수 있습니다.

5. 코드

전체 코드는 Git에 있습니다.

public int solution(int[] arr) {
	int answer = arr[0];

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

	return answer;
}

public int GCD(int number1, int number2){
	if(number1 < number2){
		int temp = number1;
		number1 = number2;
		number2 = temp;
	}

	while(number2 != 0){
		int r = number1 % number2;
		number1 = number2;
		number2 = r;
	}

	return number1;
}