PROGRAMMERES Level 1 연습문제 최대공약수와 최소공배수 (JAVA 자바)

import java.util.*;

class Solution {
    public int[] solution(int n, int m) {
        int answer[] = new int[2];
        
        int maxNum = Math.max(n,m);
        int minNum = Math.min(n,m);
        
        
        //최대공약수
        while(minNum!=0){
            int r = maxNum % minNum;
            maxNum = minNum;
            minNum = r;
        }
        
        answer[0] = maxNum;
        // 최소공배수는 n과 m을 최대공약수로 나누어주고 곱해주면 된다. 
        answer[1] = n*m / maxNum;
        
        return answer;
    }
}

두 정수  a, b(a>b)가 있을 때 a를 b로 나누었을 때의 나머지(a%b)를 r이라고 했을 때 a와 b의 최대공약수가  b와 r의 최대공약수랑 같다.

 

1. 조건인 a>b를 만족시키기 위해 큰 수를 maxNum에 초기화시켜주고 작은 수를 minNum에 초기화시켜줌
2. a와 b의 나머지(r)를 구하고 maxNum에 최솟값을 넣어주고 minNum에는 나머지(r)를 넣어준다.
3. 이런식으로 minNum이 0이 될 때까지 반복하고 이 때의 maxNum이 최대공약수이다. 
4. G(a, b) = G(b, r) 이므로 a, b의 최대공약수를 구하기 위해서 a(maxNum)에는 다음 반복문을 위해 b(minNum)을 넣어주고 minNum에는 나머지(r)를 넣어준다.  이렇게 반복하다보면 나머지(r)가 0이 되고 그 나머지가 minNum에 들어가서 반복문이 종료된다.