Hayden's Archive

[알고리즘] 프로그래머스 : N개의 최소공배수 본문

Algorithm

[알고리즘] 프로그래머스 : N개의 최소공배수

_hayden 2020. 6. 16. 19:43

알고리즘 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12953

 

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

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배��

programmers.co.kr

 

관련 포스팅 : https://hayden-archive.tistory.com/140

 

내가 작성한 코드

- 먼저 유클리드 호제법을 활용해서 재귀함수를 써서 최소공배수를 리턴하는 메소드를 작성한다.

- 아이디어 : "세 수의 최소공배수"는 "두 수의 최소공배수"와 "다른 한 수"의 최소공배수와 같다.

① 두 수의 최대공약수를 구한다. ② 최대공약수를 바탕으로 3가지 경우(서로소인 경우/작은 수가 큰 수의 최대공약수인 경우/그 외 두 수의 최대공약수가 존재하는 경우)로 나누고, 경우에 맞게 최소공배수를 구한다. ③ 그 최소공배수와 다음 수의 최대공약수를 구한다. ->반복...

class Solution {

    public int solution(int[] arr) {
        int lcm = arr[0];
        for(int i=0; i<arr.length; i++) {
        	int gcd = gcd(lcm, arr[i]);
        	if(gcd == 1) lcm = lcm * arr[i];
        	else if(Math.min(lcm, arr[i]) == gcd) lcm = Math.max(lcm, arr[i]);
        	else lcm = gcd * (lcm/gcd) * (arr[i]/gcd);
        }
        return lcm;
    }
    
    public int gcd(int a, int b) {
    	if(b==0) return a;
    	return gcd(b, a%b);
    }
}