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

📌최대공약수와 최소공배수

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

📌제한사항

• 두 수는 1이상 1000000이하의 자연수입니다.

📌입 출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

📌사용 언어 : JAVA

📌solution

class Solution {
    
    static int gcd(int a, int b){
	    if (a % b == 0) {
		    return b;
	    }
	    return gcd(b, a % b);
    }
    
    static int lcm(int a, int b){ 
        return a * b / gcd(a,b);
    }
    
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        if(n > m){
            answer[0] = gcd(n, m);
            answer[1] = lcm(n, m);
        }else{
            answer[0] = gcd(m, n);
            answer[1] = lcm(m, n);
        }
        
        return answer;
    }
}

😎풀이

gcd는 최대공약수를 구하는 함수이다. 최대공약수는 말 그대로 두 수의 공통된 약수 중 가장 큰 수를 골라야 하는 것이므로 a, b에 대해서 a > b 일 때 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 따라서 gcd를 반복하면 a와 b의 최대공약수를 반환할 수 있다.
반면lcm 최소공배수를 구하는 함수이다. 최소공배수는 두 수의 공통된 배수 중 가장 작은 수를 골라야 하는 것이기 때문에 입력받은 두 수를 곱한 값을 최대공약수로 나누어 주면 최소공배수를 쉽게 구할 수 있다.
이렇게 최대공약수와 최소공배수를 구하는 함수를 작성한 후, gcd에서 a는 b보다 커야 하므로 solution에서 n이 m보다 클 경우도 따로 구해준다. 그 후 answer에 두 함수의 리턴값을 담아주면 된다.