두 자연수 n, m이 주어졌을 때, 두 수의 **최대공약수(GCD)**와 **최소공배수(LCM)**를 구해서 배열에 담아 반환하는 문제다. 배열의 0번 인덱스에는 GCD, 1번 인덱스에는 LCM을 넣어야 한다. 처음에는 최대공약수를 1부터 min(n, m)까지 나눠보면서 찾았다. 최소공배수는 max(n, m)를 기준으로 배수를 늘려가며 두 수로 모두 나눠지는 값을 찾았다. 기존 내 코드 :

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int max = Math.max(n, m);
        int min = Math.min(n, m);
        // 최대공약수 
        for(int i=1; i<=min; i++){
            if(n%i == 0 && m%i == 0){
                answer[0] = i;
            }
        }
        // 최소공배수
        if(max%min == 0){
            answer[1] = max;
        }else{
            for(int i=2; i<=1000000; i++){
                if((max*i)%min == 0){
                    answer[1] = max*i;
                    break;
                }
            }
        } 
        return answer;
    }
}

​그런데 이건 효율이 좀 떨어진다. 유클리드 호제법을 쓰면 최대공약수는 빠르게 구할 수 있고, 최소공배수는 LCM(n,m) = GCD(n,m) / n×m 이 공식으로 구할 수 있다. 개선된 코드 :

class Solution {
    public int[] solution(int n, int m) {
        int gcd = getGCD(n, m);
        int lcm = (n * m) / gcd;
        return new int[]{gcd, lcm};
    }
    private int getGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

수학 문제는 무식하게 반복문 쓰기보다는, 수학 공식을 알고 있는지가 핵심이다. 유클리드 호제법을 활용하면 시간 복잡도도 훨씬 줄일 수 있다. 알고리즘 문제 풀 땐 무조건 공식부터 떠올리는 습관을 들여야겠다.