프로그래머스 1단계 - 최대공약수와 최소공배수

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

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

 

유클리드 호제법을 사용한다

temp를 n%m 값인 나머지라고 가정하면

GCD(n, m) == GCD(m, temp) 이된다.

n 은 이전의 m , m은 n%m 값인 temp가 들어가고, m이 0일때까지 계속 반복하면

m값이 0일때 n값이 최대공약수가 된다.

ex ) GCD(10, 3) -> GCD(3, 1) -> GCD(1, 0)

 

최소공배수 =  주어진수1 * 주어진수2 / 최대공약수

ex) 최소공배수 = n * m / temp

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        answer[0] = GCD(n, m);
        answer[1] = n * m / answer[0];
            
        
        return answer;
    }
    
    static int GCD(int x, int y){
        while(y != 0){
            int temp = x%y;
            x = y;
            y = temp;
        }
        return x;
    }
}