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

 

N개의 최소공배수

- 주어진 배열에 있는 수들의 최소공배수를 구해서 리턴하는 문제

 

※ 생각하기

- 최소공배수 구하는 방법

: 두 수(A, B)가 있을 때, 두 수의 최소공배수 =  '(A * B) / A, B의 최대공약수'이다.

 

  물론, 최대공약수와 최소공배수는 소인수분해를 활용해 구할 수 있지만 숫자가 많아질수록 너무 많은 계산이 필요하다.

그리고 우리는 로직을 통해 구현해야하므로 '유클리드 호제법(유클리드 알고리즘)'을 활용해 간단하게 최대공약수를

구할 수 있고 이를 통해 최소공배수를 구할 수 있다.

 

- 유클리드 호제법(= 유클리드 알고리즘)

: 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를

  구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을

   나타낸다.(위키백과)

 

  1) 입력으로 두 수 m,n(m>n)이 들어온다

  2) n이 0이라면, m을 출력하고 알고리즘을 종료한다.

  3) m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.

  4) 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

 

※ 풀이법

1) 유클리드 호제법을 활용해 최소공약수를 구하는 재귀함수를 만든다.

   - 재귀함수 : 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.

                   재귀 호출이나 되부름이라고도 한다.(위키백과)

   - 처음 2개의 정수(a, b)를 파라미터로 받고 b가 0이 아니라면 a와 a%b를 파라미터로 하여 자기자신을 계속해서

     호출한다. 결국 b가 0이 됬을 때 호출을 멈추고 a를 리턴하게 되는데 이 a가 바로 a와 b의 최대공약수이다.

     

2) 유클리드 호제법의 조건은 b가 a보다 커야하므로 배열이 오름차순으로 정렬이 안되있을 때를 가정하여

    Arrays.sort()로 배열을 먼저 오름차순 정렬을 해주었다.

 

3) 제일 첫 번째 수와 다음 수의 최소공배수를 먼저 구해야하므로 answer에 arr[0]을 저장한다.

 

4) 1 ~ 배열의 길이만큼 for문을 돌리며 먼저 앞 두 수의 최소공약수(gcd)를 구하고 이를 활용해 두 수의 최소공배수를

   구해 answer에 담아준다.

 

5) for문이 끝나고 answer에 담긴 값은 배열에 있는 수들의 최소공배수이다.      

 

 

기본적으로 유클리드 호제법과 재귀함수의 개념을 알고 있다면 이를 활용하는 기본적인 문제인 것 같았다.

하지만 나는 모르고 있었기 때문에(ㅠㅠ..) 문제를 통해 유클리드 호제법을 알게되었고 재귀함수의 개념과 기초적인

활용 방법을 알게 되었다.

 

import java.util.Arrays;

/**
* 2021-12-08
* 프로그래머스 level2 : N개의 최소공배수
*/
public class Solution {
	// 결과 확인을 위함
	public static void main(String[] args) {
		Solution st = new Solution();
		int[] arr = {2,6,8,14};
		System.out.println(st.solution(arr));
	}
	
	public int solution(int[] arr) {
		// 오름차순 정렬
		Arrays.sort(arr);
		
		// 첫 두수를 비교하기 위해 arr[0]을 answer에 저장
        int answer = arr[0];
        
        // arr[1]부터 for문을 돌린다
        for(int i=1; i<arr.length; i++) {
        	// 두 수의 최소공약수
        	int gcd = gcd(answer, arr[i]);
        	
        	// 두 수의 최소 공배수 : 두 수의 곱 / 두 수의 최소공약수
        	answer = (answer * arr[i]) / gcd;
        }
        
        return answer;
    }
	
	// 최소공약수를 구하는 함수
	public int gcd(int a, int b) {
		if(b == 0) {
			return a;
		}else {
			return gcd(b, a%b);
		}
	}
}