[프로그래머스] (Lv.1) 최대공약수와 최소공배수**

문제

---

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

 

-  출력 예시  -

정답 코드

---

<  내 정답 코드 1  >

class Solution {
    public int[] solution(int n, int m) {
        int[] result = new int[2];
        int min = Math.min(n, m);
        int GCD = 0;   //  최대 공약수
        int LCM = 0;   //  최소 공배수

	// for 문으로 최대 공약수 구하기
        for (int i = 1; i <= min; i++) {
            if (n % i == 0 && m % i == 0) {   //  1부터 하나씩 각 숫자로 나눠지는지 확인
                GCD = i;   //  가장 마지막으로 나눠진 값이 최대 공약수가 됨
            }
        }

        LCM = n * m / GCD;   //  최소 공배수는 최대 공약수를 통해 구함

        result[0] = GCD;
        result[1] = LCM;

        return result;
    }
}

 

<  내 정답 코드 2  >

class Solution {
    public int[] solution(int n, int m) {
        int[] result = new int[2];
        
        int min = Math.min(n, m);
        int max = Math.max(n, m);
        
        int GCD = gcd(max, min);  //  최대 공약수
        int LCM = n * m / GCD;    //  최소 공배수

        result[0] = GCD;
        result[1] = LCM;

        return result;
    }
    
    //  유클리드 호제법으로 최대 공약수 구하기
    public static int gcd(int max, int min) {
        if (max % min == 0) {   //  나머지가 0 이면 나눈 수가 '최대 공약수'가 됨
            return min;
        }
        
        return gcd(min, max % min);  //  나눈 수를 다시 나머지로 나누기
    }
}

이것을 주의하자!

---

-  일단 최대 공약수(GCD)를 구한 다음, 해당 값을 이용해서 최소 공배수(LCM)를 구하는 방식을 취한다.

[  "a 와 b의 곱은 두 값의 최대 공약수(GCD), 최소 공배수(LCM)의 곱과 같다"  ]

[  a  *  b   =   GCD  *  LCM  ]

 

    (1) 번 코드    ☞   최대 공약수(GCD)를 for 문을 통해 구한다.

 

    (2) 번 코드    ☞   최대 공약수(GCD)를 유클리드 호제법(재귀함수)로 구한다.

                     :  유클리드 호제법은 두 수의 나눗셈으로 '최대 공약수'를 구하는 방법이다.

                              a)  큰 수를 작은 수로 나눈다.

                              b)  나누는 수를 나머지로 계속 나눈다.

                              c)  나머지가 0 이 되면 나눴던 수가 '최대 공약수'가 된다.

                          

 

-  위 공식을 통해 최소 공배수를 구한다.   LCM  =  ( a  *  b )  /  GCD