[JAVA] 프로그래머스 : 최대공약수와 최소공배수

https://programmers.co.kr/learn/courses/30/lessons/12940?language=java

코딩테스트 연습 - 최대공약수와 최소공배수

풀이

최대공약수는 두 수 중 공통된 약수 중 가장 큰 자연수,
최소공배수는 두 수의 공통된 배수중 가장 작은 자연수를 의미한다.
때문에 n과 m중 더 작은 수부터 1씩 줄여나가며 둘 다 나머지가 0이 되는 수를 최대공약수로,
n*m을 최대공약수로 나눠준 수를 최소공배수로 넣어주었다.

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

유클리드 호제법과 재귀식을 사용하여 풀기

최대공약수를 구하는 재귀함수 gcd()를 만들었다.
함수에는 유클리드 호제법(최대공약수를 구하는 알고리즘)을 적용했다.

유클리드 호제법의 설명과 알고리즘 풀이는 아래의 포스팅을 참고.

[JAVA] 백준 3036번 : 최대공약수와 최소공배수

유클리드 호제법이란 서로 상대방의 수를 나누어 최대공약수를 구하는 방법으로
a%b = r(a>b) 일 때, a,b와 b,r의 최대공약수는 같다.
즉, 재귀함수로 만들어 반복해서 나눴을 때, 나머지가 0이 되는 시점의 나누는 수가 a,b의 최대공약수이다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {0,0};
        answer[0]=gcd(Math.max(n,m), Math.min(n,m)); // 최대공약수
        answer[1]=(n*m)/answer[0]; // 최소공배수
        return answer;
    }
    // 유클리드 호제법을 사용해 최대공약수 구하는 재귀함수
    public int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b,a%b);
    }
}