🤔 문제
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
❗️ 제한
- 두 수는 1이상 1000000이하의 자연수입니다.
💡 접근
최대공약수를 구하는 방법을 코드로 작성하는 것이 생각보다 쉽지 않았다. 검색해보니 유클리드 호제법이라는 것이 있었고 위키피디아에 최대공약수를 구할 수 있는 예시가 자세히 설명되어 있었다. 다른 블로그에서는 최대공약수(GCD)와 최소공배수(LCM)에 대해 자세히 설명하며 다뤄주었다. 두 내용을 간단하게 정리하면 아래와 같다.
두 수 a, b(a > b)가 존재하고 최대공약수를 구하는 함수가 GCD(a, b)이고 최소공배수를 구하는 함수가 LCM(a, b)일 때,
최대공약수(GCD)
a % b === 0이면 a, b의 최대공약수는 b가 된다.
a % b !== 0이면GCD(b, a % b)함수를 반복하여 실행하고b % (a % b) === 0이 되는 순간a % b가 최대공약수가 된다.최소공배수(LCM)
a, b의 곱에 a, b의 최대공약수로 나누어 나온 값이 a, b 두 수의 최소공배수가 된다.
LCM(a, b) = (a * b) / GCD(a, b)
최대공약수를 계산할 때 n % m === 0이 나올때까지 재귀를 이용한다. 최대공약수가 나오면 쉽게 최소공배수를 계산할 수 있다. 코드의 실행과정을 보면 n, m의 교환법칙이 성립되는 것을 확인할 수 있다. n, m의 크기와 상관없이 n % m m % n 모두 가능하다.
solution 1은 최대공약수와 최소공배수를 구하는 함수를 solution함수 밖에서 선언해 주었고, solution 2는 n, m의 교환법칙이 성립되기 때문에 max, min값을 구분하지 않고 바로 화살표함수와 삼항연산자를 이용해 더 간단하게 재귀함수를 구현한 코드이다.
이 문제는 자주 찾아보고 코드도 여러번 작성해봐야겠다.
🧑🏻💻 코드
// solution 1
// 최대공약수
function gcd(max, min) {
if (max % min === 0) return min;
if (max % min !== 0) return gcd(min, max % min);
}
// 최소공배수
function lcm(max, min) {
return (max * min) / gcd(max, min);
}
function solution(n, m) {
const max = Math.max(n, m);
const min = Math.min(n, m);
return [gcd(max, min), lcm(max, min)];
}
// solution 2
function solution(n, m) {
const gcd = (n, m) => (n % m === 0 ? m : gcd(m, n % m));
const lcm = (n, m) => (n * m) / gcd(n, m);
return [gcd(n, m), lcm(n, m)];
}
solution(12, 3); // [3, 12]
solution(2, 5); // [1, 10]📝 참고
wikipedia - 유클리드 호제법
tistory - 최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽
