(코테) 프로그래머스_N개의 최소공배수 *최소공배수 GCD , LCM

 

문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
입출력 예
arr result
[2,6,8,14] 168
[1,2,3] 6

 

 

 

 

 

최초 나의 코드 

class Solution {
    public int solution(int[] arr) {       
        int maxOrign = 0;
        int max = 0;

        for(int next:arr){
                maxOrign = Math.max(maxOrign,next);
        }

        max= maxOrign;

        while(true){   
            boolean flag = true;
            for(int i=0;i<arr.length;i++){
                if(max % arr[i] != 0){
                    max = max + maxOrign ; 
                    flag = false;
                    break;                  
                }                
            }         
            if(flag) return max;                                
        }        

    }
}

 

 

->배열의 가장 큰 값을 기준으로   배열을 순회하면서 maxOragin을 추가로 더하면서 반복문 돌림
시간복잡도가 (N*M) 으로 효율이 좋진 않다. 

다만, 문제에서 범위가 크지 않아 통과는 됐다......

 

 

 

GCD , LCM 적용

• 공약수 (GCD): 두 수가 공통으로 나눠지는 가장 큰 수
• 공배수 (LCM): 두 수가 공통으로 나눠지는 배수 중 가장 작은 수

class Solution {
    public int solution(int[] arr) {
        int lcm = arr[0];  // 첫 번째 수로 초기화
        for (int i = 1; i < arr.length; i++) {
            lcm = getLCM(lcm, arr[i]);  // 누적해서 LCM 계산
        }
        return lcm;
    }

    private int getLCM(int a, int b) {
        return a * b / getGCD(a, b);  // 최소공배수 공식
    }

    private int getGCD(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;  // 나머지를 계속 구함
            a = tmp;
        }
        return a;  // b가 0이 되면 a가 최대공약수
    }
}