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

문제

 

풀이코드

public int solution(int[] arr) {            //N개의 최소공배수
    int answer = LCM(arr[0],arr[1]);        //우선 답에 주어진 숫자배열의 첫번째, 두번째의 최소공배수를 넣는다.
    if(arr.length>1){                       //주어진 숫자의 갯수가 1개보다 많을 때,
        for(int i = 2;i<arr.length;i++){    //나머지 숫자들의 최소공배수를 구한다.
            answer = LCM(answer,arr[i]);
        }
    }else{                                  //주어진 숫자의 갯수가 1개일때,
        answer = arr[0];                    //제일 처음 주어진 수가 최소공배수이다.
    }
    return answer;
}

public int LCM(int a, int b){               //최소 공배수를 구하는 메서드
    return (a*b)/GCD(a,b);
}
public int GCD(int a, int b){               //최대공약수를 구하는 메서드(유클리드 호제법을 이용)
    if((a%b) == 0){
        return b;
    }else{
        return GCD(b,a%b);
    }
}

이렇게 풀었는데 이게 원리만 알면 생각보다 쉽게쉽게 풀 수 있다!

 

우선 최소공배수를 구하는 방법은 간단히 몇몇의 수들을 인수분해 한다음에 구해보면 알지만

두 수의 곱/두 수의 최대공약수 이 공식을 쓰면 두 수의 최소공배수가 나온다.

 

그래서 두 수의 최대공약수를 구하는 메서드 GCD를 만들었는데 두 수의 최대공약수를 구하는 방법은

유클리드 호제법을 이용하여 메서드를 만들었다.

유클리드 호제법에 관련된 내용은 https://github.com/crupy/TIL/blob/master/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EC%8B%A4%EC%A0%84%20%EA%B0%9C%EB%85%90/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95.md

GitHub - crupy/TIL: Today I Learned. 하루하루 공부한 내용들을 정리

여기에 포스팅을 해놓았다.

 

이렇게 최대공약수, 최소공배수만 구하면 이제 문제는 다 풀었다.

처음 두 수의 최소공배수를 구하고, 그 최소공배수와 그다음 수의 최소공배수를 구하고, 이것을 반복하면 여러 숫자들의 최소공배수를 쉽게 구할 수 있다.