개인공부-14

1. N개의 최소공배수

• [2,6,8,14]이런식의 15개 이하 100이하의 숫자로 구성된 배열이 주어질 때 최소공배수를 구하는 문제

2. 처음 잘못된 발상

• 단순하게 생각해서 배열을 오름차순 정렬한 후 1을 제외한 최소의 숫자로 전부 나눠 떨어진다면, 그 숫자가 최대공약수라고 생각했고, 그 수로 나눈 값을과 최대공약수의 곱을 리턴하게 했다.
• 이 때 예외 케이스 [3,4,9,16] -> 이 경우는 최소공배수가 144이다.
• 한번에 최대 공약수를 구하는 것이 아닌 처음부터 단계적으로 구해야 한다는 것을 깨닳았음!!!!!!

3. 수정 발상

• 처음부터 진행하되, 유클리드 호재법을 사용하여 최대공약수를 구하면서 진행했다.
• ex) 3,4 -> 최대 공약수 1 , 최소공배수 12 -> 12,9 -> 최대공약수 3, 최소공배수 36 ...
• 느낀점 : 많은 수의 최대공약수나, 최소공배수를 구할 때는 한번에 하지말고 처음부터 단계적으로 구하자...

4. 완성코드

 public int solution(int[] arr) {


        Arrays.sort(arr);
        int tot = arr[0];

        for(int ar : arr){
            int max = sol(tot,ar);
            tot = max * (tot/max) * (ar/max);
            System.out.println(tot);

        }

        return tot;

    }

    public int sol(int a,int b){

        int first = Math.max(a,b);
        int second = Math.min(a,b);
        int res = 0;

        while(first%second!=0){
            res = first % second;
            first = second;
            second = res;
        }

        return second;



    }