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

풀이 과정

1. 최대공약수 구하기: 유클리드 공식
2. 최소공배수 구하기: 두 수의 곱 / 최대 공약수

코드

function getGcd(a, b) {
  const r = a % b;
  return r === 0 ? b : getGcd(b, r);
}

function solution(n, m) {
  const gcd = n > m ? getGcd(n, m) : getGcd(m, n);
  return [gcd, (n * m) / gcd];
}

🦾

풀 때마다 유클리드 공식이 뭐였더라 하고 찾아보는 나...
이제 진짜 기억해둘 겸 메모

• 두 수의 최대공약수는 큰 수를 작은 수로 나눈 나머지와 작은 수 사이의 최대공약수와 같다.

1. 두 수 중 큰 수, 작은 수 판별
2. 큰 수를 작은 수로 나누어 나머지 구하기
   나머지가 0이면 작은 수가 최대공약수
   나머지가 0이 아니면 나누기 반복 (재귀)

🤔

처음에는 재귀 함수 내부에서 Math.max()와 Math.min()을 매번 호출했다.
다른 사람 코드들을 본 후 처음에 한 번만 판단하면 그 이후부턴 큰 수와 작은 수가 고정이 된다는 걸 알고 수정했다.