[프로그래머스] 최대공약수와 최소공배수 자바 유클리드 호제법

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

프로그래머스

문제

주어진 두 수의 최대공약수와 최소공배수를 배열에 담아 반환하시오.

접근

각 수의 약수 리스트를 먼저 구한 후, 반복문으로 m의 약수 목록에 n의 약수가 존재하는지 체크하고 촌재하면 최대값을 갱신 -> 최대공약수

 

최소공배수는 (n * m) / 최대공약수를 활용했다.

 

public static int[] solution(int n, int m) {
        List<Integer> nFactors = getFactors(n);
        List<Integer> mFactors = getFactors(m);
        int maxFactor = 1; // 최대 공약수
        int minMulti = 1;
        for(int x : nFactors){
            boolean isExist = mFactors.contains(x);
            if(isExist){
                maxFactor = Math.max(maxFactor, x);
            }
        }
        //최소공배수 공식 : (n * m) / 최대공약수
        minMulti = (n * m) / maxFactor;
        return new int[]{maxFactor, minMulti};
    }

    //제곱근으로 약수구하기
    public static List<Integer> getFactors(int n){
        List<Integer> factors = new ArrayList<>();
        for(int i = 1; i <= Math.sqrt(n); i ++){
            if (n % i == 0) {
                factors.add(i);
                if (i != n / i) { // 중복 제거 (예: 5x3, 3x5)
                    factors.add(n / i);
                }
            }
        }
        Collections.sort(factors);
        return factors;
    }

발견된 문제 : 더 효율적인 방법

최대공약수를 구할 더 효율적인 방법이 있었다. 유클리드 호제법이라고 한다.

//유클리드 호제법을 이용한 최대공약수 계산
    public int getGCD(int n, int m){
        while ( m != 0) {
            int temp = n % m ;
            n = m;
            m = temp;
        }
        return n;
    }

개선

public static int[] solution2(int n, int m){
        int gcd = getGCD(n, m);
        int lcm = (n * m) / gcd;
        return new int[]{gcd, lcm};
    }