오늘의 코딩테스트 (최대공약수와 최소공배수)

 

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

 

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int a = Math.max(n, m);
        int b = Math.min(n, m);
        int gcd = 0;
        int lcm = 0;
        
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        gcd = a;
        
        lcm = (n * m) / gcd;
        
        answer[0] = gcd;
        answer[1] = lcm;
        
        return answer;
    }
}

 

최대공약수는 유클리드 호제법으로 구했다.

1. A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구한다.
2. B를 R1으로 나눈 나머지 R2를 구한다.
3. R1을 R2로 나눈 나머지 R3를 구한다.
4. 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복한다. 이 직전 얻은 나머지가 최대공약수이다.

최소공배수는 두 수가 공통으로 가지고 있는 배수 중 가장 작은 수 이므로, 두 수를 곱한 값을 최대 공약수로 나눈 수와 같아 최대공약수를 구한뒤 구해주었다.

 

 

다른 풀이

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        for (int i = 1; i < n + m; i++) {
            if (n % i == 0 && m % i == 0) {
                answer[0] = i;
                answer[1] = n * m / answer[0];
            }
        }
        return answer;
    }

}