Programmers Level 1 - 최대공약수와 최소공배수

문제 설명

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

 

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예 

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = gcd(n, m);
        answer[1] = lcm(n, m);
        return answer;
    }
 
    public int gcd(int a, int b) { // 최대 공약수
        return a % b == 0 ? b : gcd(b, a % b);
    }
 
    public int lcm(int a, int b) { // 최소 공배수
        // 0이 아닌 두수의 곱/두수의 최대 공약수
        return (a * b) / gcd(a, b);
    }
}

 

두개의 메서드를 작성하였다.     유클리드 호제법을 이용하여 재귀호출로  최대 공약수를 구하는 메서드를 만들었습니다.     최소 공배수 = 두수의 곱/최대공약수

 

유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.   유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를   구하 는 알고리즘의 하나이다.    호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.   일반적으로 최대공약수를 구하기 위해선 먼저 소인수분해를 해야한다.   1112 = 139 X 2 X 2 X 2   695 = 139 X 5   두 수를 소인수분해한 후, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수(GCD)는 139인 것을 알 수 있다.   이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다.   유클리드 호제법 사용하기   유클리드 호제법을 이해하기 위해서는 MOD연산에 대해 알고 있어야 한다.   MOD연산이란? 두 값을 나눈 나머지를 구하는 연산!   먼저, 큰 수를 작은 수로 나눈 나머지를 구한다. 즉, MOD 연산을 한다.   1112 mod 695 = 417   그 다음, 나눴던 수와 나머지로 또 MOD 연산을 한다.   695 mod 417 = 278   이 과정을 계속 반복한다.   417 mod 278 = 139   278 mod 139 = 0   나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다.   간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하면 된다!

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int i = Math.min(n,m); 
        for (;i>=0; --i) {
            if (n % i == 0 && m % i == 0) break;
        }
        answer[0] = i;
        answer[1] = n * m / i;
        return answer;
    }
}

줄이면 이렇게

 

class Solution {
    public int[] solution(int n, int m) {
        int i = Math.min(n,m); 
        for (;i>=0; --i) {
            if (n % i == 0 && m % i == 0) break;
        }
        return new int[]{i, n*m/i};
    }
}

 

적은수 보다 큰 수는 공약수가 될수 없으므로 두수 중에서 제일 적은 값부터 1씩 줄어 들면서 반복합니다.    둘 다 나누어떨어지면 그 수가 최대 공약수 입니다.  반복문을 탈출합니다.    최소 공배수 = 두수의 곱/최대공약수입니다.