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

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

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

class Solution {
	    public int solution(int[] arr) {
	        
	        int size=arr.length;
	        
	        int num1=arr[0];
	        for(int i=1; i<size; i++) {
	        	int num2=arr[i];
	        	
	        	int max=Math.max(num1,num2);
	        	int min=Math.min(num1,num2);
	        	
	        	num1=max*min/gcd(max,min);
	        	
	        }
	        return num1;
	    }

		private int gcd(int max, int min) {
			while(min!=0) {
				int r=max%min;
				max=min;
				min=r;
			}
			return max;
		}
	}

소요시간 : 20분 

 

유클리드 호제법을 이용하였다.

 

유클리드 호제법이란 두개의 수 a, b 가 있을 때 최소공약수를 구하는 방법이다.

최대공배수는 (a*b)/최대공약수로 구할 수 있다.

 

a, b 중 큰수를 max, 작은수를 min에 넣는다.

 

그리고 min은 다음 gcd함수에서의 max가 된다 

그리고 max%min은 다음 gcd함수에서 min이 된다.

이렇게 하다가 min이 0이되면 그때의 max가 최대공약수다.

 

예를 들어 10 과 8이 있다고 해보자

 

max : 10   min : 8

max : 8     min : 10%8=2

max : 2     min : 8%2 = 0

 

return max(2)

 

이렇게 10과 8의 최대공약수는 2 최대공배수는 (10*8)/2 = 40이 된다!