🖥️ 프로그래머스 - 최대공약수와 최소공배수
-
문제
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
-
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
-
입출력 예시
- 입출력 예 #1
n m return
3 12 [3, 12]
2 5 [1, 10] - 입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
- 입출력 예 #1
문제 접근 방식
최소공약수 최대공배수 언제 배운 건지 까마득해서 검색까지 해봤다.
- 최대 공약수 : 두 수 A와 B의 공통된 약수 중에 가장 큰 정수
- 최소 공배수 : 두 수 A와 B의 공통된 약수 중에 가장 작은 정수
for문 돌려서 찾을 수도 있겠지만 더 쉬운 공식이 없나? 싶어서 찾아봤더니 역시나 공식이 있었다.
작은 수 b로 큰 수 a를 나누었을 때 나오는 나머지 r로 다시 b를 나누고 그 나머지인 r2로 r을 나누는 것을 반복한다. 마지막에 나머지를 0으로 만드는 수가 최대공약수.
- 유클리드 호제법
a % b .. r
b % r .. r2
r % r2 .. r3
...
rx % rn .. 0
rn = 최대공약수최대공약수만 구하면 최소공배수는 쉽게 구할 수 있었다. 두 수를 곱하고 최대공약수로 나누어주면 된다.
작성한 정답 코드
function solution(n, m) {
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const lcm = (n * m) / gcd(n, m);
return [gcd(n, m), lcm];
}
- const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b)
최대공약수를 구하는 재귀함수 나머지가 0이 되면 0이 되게 한 수를 리턴함- const lcm = (n * m) / gcd(n, m)
최소공배수를 구하는 공식- return [gcd(n, m), lcm]
배열 형태로 리턴하기
