[2020-11-20] 최대공약수와 최소공배수

푼 시간 : 40분

언어 : 자바

 

---

 

 

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

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

 

도저히 어떻게 하는지 몰라서 고민하다가 인터넷에 유클리드 호제법을 검색해 봐서 풀었다.

최소 공배수와 최대 공약수를 구하는 방법이 너무 많기때문에 if문을 도배 할 수 없고,

유클리드 호제법을 쓸 수밖에 없었다. 처음 보자마자 재귀함수를 써야 한다고 느꼈으나,

도저히 어떤방식으로 써야할지 감이 안잡혔었다.

 

천천히 고민하면서 재귀함수를 쓰다 보니 잘 된 것 같다.

재귀함수의 구조에 대해서 완벽히 이해하지는 못했지만 재귀함수를 썼다는것에

의의를 두고 푼 문제인 것 같다!

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        answer[0]=(m>n||n>m)?gcd(m, n):gcd(n, m);
        // m이크면 a가m, n이크면 b가n
        answer[1]=(m*n)/answer[0];
        // 최대공배수는 m*n / 최대공약수
        
        return answer;
    }
    
    public int gcd(int a, int b){
        if(a%b==0)
        // 최대공약수는 나머지가 0인수
            return b;
        else
        // 나머지가 0이 아니면 재귀호출한다.
            return gcd(b, a%b);
    }
}