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

https://programmers.co.kr/learn/courses/30/lessons/12940

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

 

최대공약수 -> 유클리드 호제법 이용

최소공배수 -> n*m/최대공약수

 

유클리드 호제법

유클리드 로제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

자연수 a,b(a>b)에 대하여 a를 b로 나눈 나머지가 r일때 a,b의 최대공약수와 b,r의 최대공약수가 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a,b의 최대 공약수이다.

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

ex) 25와 15의 최대공약수

• 25와 15는 나누어떨어지지 않으므로 25를 15로 나눈 나머지 -> 10
• 15와 10는 나누어떨어지지 않으므로 15를 10로 나눈 나머지 -> 5
• 10와 5는 나누어 떨어지므로 나머지가 0이 된다
• 따라서 최대공약수는 5이다.

 

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); // 작은 수
        
        while(b > 0){
            int temp = b;
            b = a % b;
            a = temp;
        }
        
        answer[0] = a;
        answer[1] = n*m/a;
        
        return answer;
    }
}

 

 

다른 풀이 (재귀함수)

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);
 
        answer[0] = gcd(a, b);
        answer[1] = n*m/answer[0];
        
        return answer;
    }
    public int gcd(int p, int q){
        if(q == 0) return p;
        return gcd(q, p%q);
    }
}