[programmers] N개의 최소공배수

N개의 최소공배수

 
x
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요. 예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.

 

내가 처음으로 메서드를 두개 만들어서 푼 문제가 아닐까 싶다. 원래 한 메소드에다가 다풀었었는데 다들 메소드 두 개로 나누어서 풀길래 보기에도 더 예쁘고 더 간편해보여서 나도 나눠봤다.

두 개의 수로 최대공약수와 최소공배수는 앞에서 구했었는데, 여러개는 어떻게 해야하지.. 하는데 의외로 단순했다. 우선 두 개의 수로 최대공배수를 구하고, 그 최대공배수와 다른 수로 최대공배수를 구하고, 또 그 최대공배수와 다른 수로 최대공배수를 구하는 식으로 계속 구해나가면 되는 거였다.

 

 
x
class NLCM {
    
    public long nlcm(int[] num) {
        long answer = num[0];
        long small = 0;
        long big = 0;
        
        for (int i = 1; i < num.length; i++) {
            small = Math.min(answer, num[i]);
            big = Math.max(answer, num[i]);
            
            answer = (small * big) / gcd(small, big);
        }
        
        return answer;
    }
    
    public static long gcd(long small, long big) {
        long answer = 0;
        
        for(int i = 1; i <= small; i++){
            
          if(small % i == 0 && big % i == 0) answer = i;
        }
        
        return answer;
    }
​
    public static void main(String[] args) {
        NLCM c = new NLCM();
        int[] ex = { 2, 6, 8, 14 };
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(c.nlcm(ex));
    }
}