프로그래머스 - 최대공약수와 최소공배수

최대공약수 구하는 걸 모르겠어서 그냥 바로 참고했다.

너무 길어 보이는데, 다 주석이다.

1. 유클리드 호제법

- 최소공배수 = (n * m) / 최대공약수

- 최대공약수 두 수의 나머지를 이용해 순환

2. 유클리드 호제법 사용 전에,, 두 수를 정렬할 필요 X(정렬 해야할 것 같았다.)

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        /**
         * 필요없는 부분
         */
//        if (n > m) {
//            tmp = m;
//            m = n;
//            n = tmp;
//        }

        answer[0] = gcd(n, m);
        answer[1] = lcm(n, m);
        return answer;
    }

    /**
     * 최소공배수 = (s * b) / 최대공약수
     * @param s
     * @param b
     * @return
     */
    public static int lcm(int s, int b) {
        return (s * b) / gcd(s, b);
    }

    /**
     * 최대공약수
     *
     * 두 수 크기를 사전에 정렬할 필요 X!
     * @param s
     * @param b
     * @return
     */
    public static int gcd(int s, int b) {
        int r;

        while (s != 0) {
            r = b % s;
            b = s;
            s = r;
        }

        return b;
    }
}