23/12/05 TIL __ 유클리드 호제법

 

 

알고리즘을 풀다가 최대공약수, 최소공배수 문제를 만낫다. 

레벨 1 문제였지만 시간이 꽤 걸렸다. 

사실 간단한 수학적 원리를 알고있었다면 좀더 효율적으로 풀었을 것 같다. 

 

 

문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
입출력 예 n m (3, 12) return[3, 12] 
               n m(2, 5) return[1, 10]
입출력 예 #2자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

 

아래는 처음 풀어낸 해결방법이다. 

function solution(n, m) {
    let small = [1, 1, n, m]
    let big = [n, m]
    function makeSmall(x){
        for(let i=2; i<=Math.ceil(x/2); i++){
            if(x%i ===0) {
                small.push(i)
            }else if(x%i !==0){}
        }
        return small.sort((a,b)=> b-a);
    }
    function makeBig(x){
        let i=2;
        let a;
        x===n ? a=m : a=n;
        while(new Set(big).size  ===  big.length){
            if((x*i)%a !==0){
                big.push(x*i);
                i++; 
            }else if((x*i)%a ===0){
                big.push(x*i);
                i++; 
                return big
            }
        }
    }
    makeSmall(n)
    makeSmall(m)
    if(n> m){
        makeBig(m)
        makeBig(n)
    }else{
        makeBig(n)
        makeBig(m)
    }

    let finallySmall = small.filter((e,i)=>{return e=== small[i+1]})
    return [finallySmall[0],big.sort((a,b)=>b-a)[0] ]
}