[프로그래머스] Lv.1 최대공약수와 최소공배수 (JavaScript)

🔐 문제

두 수 n과 m을 입력받아, 두 수의 최대공약수와 최소공배수를 반환하는 함수를 완성하라.

• 예시
  n이 3이고, m이 12일때 solution 함수는 [3, 12]를 반환해야 한다.

🔑 풀이

function findGCD(n, m){
    // 최대공약수 구하기
    if (n%m === 0) {
        return m;
    } else {
        return findGCD(m, n%m)
    }
}

function solution(n, m){
    let answer = [];
    let GCD = findGCD(n, m); // 최대공약수
    let LCM = n * m / GCD; // 최소공배수
    answer.push(GCD);
    answer.push(LCM);
    return answer;
}

1. 유클리드 호제법으로 최대공약수를 먼저 구합니다.
   • n > m 일때, n을 m으로 나눈 나머지를 r이라고 합시다.
     ◽ r = 0인 경우 : n과 m 중 작은 수인 m이 두 수의 최대공약수 입니다.
     ◽ r = 0이 아닌 경우 : 작은 수 m과 나머지 r의 나머지를 구해 위 과정을 반복해줍니다.
   • 재귀함수로 위 과정을 반복할 수 있도록 만들어줍니다.

2. 주어진 두 수인 n과 m의 곱하고 최대공약수로 나누어 최소공배수를 구해줍니다.

💡 배운점

유클리드 호제법을 통해 최대공약수를 간단하게 구할 수 있는 방법에 대해 익힐 수 있었다.