[Algorithm] 최대공약수&최소공배수 구하기 - 유클리드 호제법

문제

배열로 주어지는 N개의 수들의 최소공배수 구하기

프로그래머스

---

풀이

• 최대공약수 : 여러 수들의 공통적인 약수 중 가장 큰 수
• 최소공배수 : 여러 수들의 공통적인 배수 중 가장 작은 수
• 최대공약수는 유클리드 호제법으로 구해야한다 (이건 그냥 이해하려고 하기보다는 외워야할 것 같다 (gcd 함수))
• 최소공배수는 대상이 되는 두 수의 곱을 최대공약수로 나눈 수이다 (이것도 그냥 외우자..)

코드

public class SkillCheck_2_1 {

	static public int gcd(int a, int b) { // 최대공약수를 구하는 함수
		while(b !=0 ) {
			int r = a%b; // 두 수를 나눈 나머지
			a = b;
			b = r;
		}
		return a;
	}
	
	static public int lcm(int a, int b) { // 최소공배수를 구하는 함수
		return (int)a*b/gcd(a, b); // 두 수를 곱한 값을 최대공약수로 나눈 값이 최소공배수
	}
	
	public int solution(int[] arr) {
	      int answer = 0; 
	      int temp = arr[0]; // 임시변수
	      
	      for (int i=1; i<arr.length; i++) {
	    	  temp = lcm(temp, arr[i]); // 앞에서 이미 구한 최소공배수와 값을 비교하면 최종 최소공배수가 나옴
	      }
	      
	      answer = temp;
	      return answer;
	      
	}
}