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

최대공약수와 최소공배수

내가 쓴 답

생각보다 너무 긴 것 같아 다른 사람 것을 찾아 봤다.

public class Solution {
    public int[] solution(int n, int m) {
        int min = 0;
        int max = 0;
        if (n < m)
        {
            return ReturnMinMax(n, m);
        }
        else
        {
            return ReturnMinMax(m, n);
        }
    }
    
    private int[] ReturnMinMax(int n, int m)
    {
        int min = 0;
        for (int i = 1; i <= n; i++)
        {
            if (n % i == 0 && m % i == 0)
            {
                min = i;
            }
        }

        int j = 1;
        int max = 0;
        while (true)
        {
            if (m * j % n == 0)
            {
                max = m * j;
                break;
            }

            j++;
        }

        return new int[] { min, max };
    }
}

 

다른 사람 풀이

a%b가 딱 떨어지면 최대 공약수인 것이고 안 나눠지면 작은 수와 큰수%작은수 한 값을 다시 재귀로 뽑아내는 것이 중요한 것 같다.

public class Solution {
    public int[] solution(int n, int m) {
        int _gcd = gcd(n, m);
        int[] answer = new int[] {_gcd, n * m / _gcd};

        return answer;
    }

    int gcd(int a, int b)
    {
        return (a % b == 0 ? b : gcd(b, a % b));
    }
}