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

문제

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

나의 풀이

function solution(n, m) {
    var answer = [];
    let arr1 =[];
    let arr2 =[];
    let val1 = n;
    let val2 = m;
    let q = 2;
    do{
        if (val1 % q ==0 ){
            arr1.push(q)
            val1 = val1/q
        } else{
            q += 1
        }
    } while( val1 > 1)
    // console.log(arr1)
    q = 2;
    do{
        if (val2 % q ==0 ){
            arr2.push(q)
            val2 = val2/q
        } else{
            q += 1
        }
    } while( val2 > 1)
    // console.log(arr2)

    let Gmax = arr1.reduce((acc,cur)=> {
        if (arr2.indexOf(cur) !== -1){
            arr2[arr2.indexOf(cur)] = 0
            return acc * cur;
        }
        return acc
    },1)
    // console.log("Gmax:",Gmax)

    let Lmin = (n*m) /Gmax
    // console.log(Lmin)

    answer.push(Gmax)
    answer.push(Lmin)

    return answer;
}

 

일일이 나눠지는지 판단하고, 나눠지는 수들을 모아둔다.
모아둔 배열에서 겹치는 부분을 통해 최대공약수를 구하고
이후 최소공배수를 구했다.

 

최소공배수 * 최대공약수 = A * B (두 수)

다른 이들의 풀이

유클리드 호제법을 이용한 코딩을 하였다.

 

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)];
}

 

유클리드 호제법

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어떨어진다.
따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

 

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 ＋ 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 ＋ 0

 

따라서, 최대공약수는 36이다.