문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
입출력 예 설명
입출력 예 #1
위의 설명과 같습니다.
입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
sol)
function solution(n, m) {
var answer = [];
answer.push(GCD(n,m));
answer.push(LCM(n,m));
return answer;
}
// 최대 공약수
function GCD(n,m) {
let answer = 1;
for (let i = 2; i <= findMin([n,m]); i++) {
if (n % i === 0 && m % i === 0) {
answer = i;
}
}
return answer;
}
// 최소 공배수
function LCM(n,m) {
let answer = 1;
while(true) {
if (answer % n === 0 && answer % m === 0) {
break;
}
answer ++;
}
return answer;
}
function findMin(array) {
// 배열이 비어있으면 undefined 반환
if (array.length === 0) return undefined;
// 첫 번째 요소를 최소값으로 초기화
let min = array[0];
// 배열을 순회하면서 각 요소를 현재의 최소값과 비교
for (let i = 1; i < array.length; i++) {
if (array[i] < min) {
min = array[i]; // 새로운 최소값 발견
}
}
return min;
}
유클리드 호제법을 이용한 구현
유클리드 호제법의 기본 원리는 num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다.
r이 0이라면, 그 때의 num2가 최대공약수이다.
num1=24, num2=16을 가정하면, GCD(24, 16) = GCD(16, 8) = GCD(8, 0)
GCD = 8
let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);
여기서 num1 < num2의 경우에는 값이 자동스왑된다. ex) num1=16, num2=24일 경우에는 getGCD(24, (16%24=16))이 불러지게 된다.
단순의 내가 적은 solution 방식으로 하는 것보다 유클리드 호제법을 잘 알고 있었더라면 더 쉽고 효율적으로 구현할 수 있었을 것 같다..
