최대공약수와 최소공배수

❔문제 설명

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

제한사항

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

---

풀이

처음엔 1부터 시작해서 하나씩 체크하려고 했는데 제한사항을 보고 바로 포기했다😅

생각해봐도 모르겠어서 검색해보니 유클리드 호제법을 이용하면 쉽게 해결할 수 있다고 한다.

📕유클리드 호제법?

2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘 중 하나로 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻을 수 있는 알고리즘이다.

예를 들어 1230과 428이 있다고 했을 때

1230 % 428 = 374
428 % 374 = 54
374 % 54 = 50
54 % 50 = 4
50 % 4 = 2
4 % 2 = 0

이 때 나머지가 0이 되기 직전에 나눈 숫자인 2가 1230과 428의 최대공약수이다.

소인수분해를 통해 확인해보자면

• 1230 = 2 3 5 * 41
• 428 = 2 2 107

로, 두 수의 최대공약수가 2가 맞다는 걸 확인할 수 있다.

이 알고리즘을 적용해서 문제를 풀면

function solution(n, m) {
    const getGCD = (a, b) => b > 0 ? getGCD(b, a % b) : a
    const getLCM = (a, b) => a * b / getGCD(a, b)
    
    let gcd = n > m ? getGCD(n, m) : getGCD(m, n)
    let lcm = n > m ? getLCM(n, m) : getLCM(m, n)
    
    return [gcd, lcm]
}

이렇게 작성할 수 있다.

그런데 통과 후 궁금해서 좀 더 찾아봤는데 a, b에 들어올 값 중에 어떤 게 큰지 굳이 체크하지 않아도 자동으로 넘어가진다고 하는데 왜 그렇게 되는건지 아직 이해는 안된다...🤔

✔문제출처: 프로그래머스