Algorithm | 최대공약수와 최소공배수

문제 설명

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

제한 조건

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

예시

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

📍 나의 풀이1

유클리드 호제법을 쓰지 않은 풀이법

function solution(n,m){
  const bigger = Math.max(n,m);
  const smaller = Math.min(n,m);
  
  let GCD = 1;
  let LCM = 1;
  
  for(let i = smaller; i>=1; i--){
    if(bigger%i ===0 && smaller%i ===0 ){
      GCD = i; 
    }
  }
  LCM = (n*m)/GCD
  return [GCD,LCM]
}

📍 나의 풀이2

처음 풀이하고 나서 알게된 재귀함수를 이용
유클리드 호제법 + 재귀함수

const getGCD = (a,b) => {
  if(a%b !== 0){
    return getGCD(b,a%b)
  }else{
    return b
  }
}
const getLCM = (a,b) => {
  return (a*b)/getGCD(a,b)
}
function solution1(n,m){
  const bigger = Math.max(n,m);
  const smaller = Math.min(n,m);
  return [getGCD(bigger,smaller),getLCM(bigger,smaller)]
}

📍다른 풀이

function greatestCommonDivisor(a, b) {
  return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);
} 

function leastCommonMultipleOfTwo(a, b) {
  return (a * b) / greatestCommonDivisor(a, b);
} 

function gcdlcm(a, b) { 
  return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)]; 
} 

// ⬇️ 나의 풀이2와 비슷할 꼴로 변경
const getGCD = (a,b) => { //1: a,b 2: a =>b,b =>a%b
 return b?getGCD(b,a%b):a; // b => remainder
}
const getGCD = (a,b) => {
  if(a%b !== 0){
    return getGCD(b,a%b)
  }else{
    return b
  }
}
const getLCM = (a,b) => {
  return (a*b)/getGCD(a,b)
}
function solution1(n,m){
  const bigger = Math.max(n,m);
  const smaller = Math.min(n,m);
  return [getGCD(bigger,smaller),getLCM(bigger,smaller)]
}

getGCD 함수 리턴 부분에서 return값이 달라서 처음에 이해하는데 조금 헷갈렸다.

나는 a,b의 나머지 값에 따라서 0일때 b를 리턴하였고,
다른 분의 풀이에서는 어차피 재귀를 통해서 getGCD가 호출되기 때문에 인자 b에 0이 들어올때는 같이 들어오는 a가 최대공약수일 것이다.
그래서 a를 리턴했다.

[참고자료 | 최대공약수와 최소공배수 (Level 1)]