프로그래머스 Java : N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

---

...사실 이러면 안 되지만 숫자 범위가 완전 만만하기 때문에 그냥 반복문 돌렸어여

아니? 안 될 일은 아니지?

 

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        int t = arr[0];
        while(true){
            boolean p = true;
            for(int i=0;i<arr.length;i++)
                if(arr[i]%t!=0) p=false;
            if (p) break;
            t--;
        }
        answer=t;
        while(true){
            boolean p = true;
            for(int i=0;i<arr.length;i++)
                if(answer%arr[i]!=0) p=false;
            if (p) break;
            answer+=t;
        }
        return answer;
    }
}

 

근데 안 하는 게 좋고요

유클리드 호제법을 사용합시다.

class Solution {
    public int solution(int[] arr) {
        int lcm = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            lcm = getLcm(lcm, arr[i]);
        }
        
        return lcm;
    }

    // 최소공배수 = (a * b) / 최대공약수
    private static int getLcm(int a, int b) {
        return (a * b) / getGcd(a, b);
    }

    // 유클리드 호제법 (최대공약수)
    private static int getGcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

외워야하는데 잘 안 댐 맘처럼 그게 되는 게 아냐