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

문제 링크

programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

문제 풀이

최대공약수를 구하는 유클리드 호제법만 알고 있다면 어렵지 않게 풀수 있는 문제다.

 

유클리드 호제법이란? 

 

두 수 A,B가 있을때 그 중 큰수를 A로 두고 작은수를 B로 두자.

 

A % B를 했을때 나머지가 0 이된다면 B가 최대공약수이고 그게 아니라면

 

B를 A위치로 두고, A%B를 B위치로 두고 나머지가 될 때까지 반복한다.

 

 1. 두 수중 큰수를 A, 작은수를 B로 둔다.

 

 2-1. A % B 가 0이 나오면 B를 최대 공약수로 return한다.

 

 2-2. A % B 가 0이 아니라면 B를 A로 두고 A%B를 B로 둔다.

 

 3. 2번을 반복한다.

 

최대 공약수를 구한다면 어렵지 않으므로 나머지 내용은 소스코드를 보면서 이해 해보면 되겠다.

소스 코드

public class Sol {

	public int solution(int[] arr) {
        int answer = 1;
        for (int i : arr) 
			answer = answer * i /GCD(answer, i);
        return answer;
    }
	
	public static int GCD(int a, int b) {
		int max = Math.max(a, b);
		int min = Math.min(a, b);
		
		if(max % min == 0) return min;
		else return GCD(min, max%min);
		
	}

}