[프로그래머스-JS] level.1 최대공약수와 최소공배수 <*>

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

 

 

실패한 코드 

 

function solution(n, m) {
    let gcdN = [];
    let gcdM = [];
    for(i=1; i<= n; i++){
        if(!(n % i)) gcdN.push(i)  
    }
    for(k=1; k<= m; k++){
        if(!(m % k)) gcdM.push(k)
    }
    let lcmN =[];
    let lcmM =[];
    for(x=1; x<= m*n; x++){
        lcmN.push(n*x);
        lcmM.push(m*x);
    }
    const lcm = lcmN.find(y=> lcmM.find(v => v === y))
    const gcd = gcdN.filter(x=> gcdM.find(v => v ===x))
    return [gcd[gcd.length -1],lcm];
}

이 풀이는 다 통과하는데 테스트케이스 11에서 마지막까지 시간초과 때문에 실패햇다. 

 

풀면서도 무슨 알고리즘이 있었던 것 같든데 알고리즘 안쓰고도 풀어보고 싶었지만 실패!

 

나중에 여기서 시간 복잡도만 줄이면 될 것 같다

 

유클리드 호제법으로 푼 풀이

 

function solution(n, m) {
    const gcd = (a,b) =>{
        const remainder = a%b;
        if( remainder === 0) return b;
        return gcd(b, remainder)
    }
    return [gcd(n,m),n*m/gcd(n,m)];
}

 

유클리드 호제법은 원리가 간단하다. 

 

1. 두 수 중에서 큰 수를 작은 수로 나눈다. 

2. 만약 나누고 난 나머지가 0이라면 작은 수가 최대공약수이다.

3. 만약 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눈다. 

4. 이를 반복해서 나머지가 0이 될 때, 그 수가 바로 두 수의 최대공약수이다.

 

 

위 코드에서는 작은 수 큰 수 구분을 하지 않았다. 

왜냐하면 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫이 0이 되고 그 자신이 나머지가 되기 때문이다. 

 

예를 들어 

let a = 9
let b = 10

// a < b 인 상태이다. 

console.log(a%b) // 9

//이걸 gcd 함수에 넣는다고하면

const gcd = (a,b) =>{
        const remainder = a%b;
        if( remainder === 0) return b;
        return gcd(b, remainder)
    }
    
gcd(9,10)

// remainder가 9%10 이기에 9가 할당된다. 
// 그리고 b= 10이었기에  b에 10이 할당되고 두 번째 인자에  remainder가 할당된다.
// 즉 g(10,9)가 된다. 
// 이렇기에  어떤게 큰수인지 확인할 필요가 없는 것이다.

 

마지막으로 최소공배수는    두 수를 곱하고 최대공약수로 나눠주면 된다. 

 

다른 사람 풀이 

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

이분은 for문은 잘 이해하고 있으신 분이다. 

 

첫 번째는 선언문 

두 번재는 조건문

세 번째는 증감문이다. 

네 번재인 실행문이 없어서  이 for문은  조건문이 false되는 순간 끝난다. 

즉 조건문이 false되기 전까지 증감문을 이용해서  a 와 b 를 다루고 있다.

선언문에서 ab = a*b 라고 해준뒤 

조건문에서 r = a % b 로 해줬다. 위 유클리드 호제법을 함수로 만든 것을 여기는 for문으로 만든것이다. 

증감문은  a=b, b =r로 해주었다. 

 

예제로 이해해보자

 

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){
		console.log(ab, "ab");
		console.log(r,"r")
		console.log(a,b,"a,b")
		console.log("====cur====")
	}
    return [b, ab/b];
}

console.log(gcdlcm(9,10))

//90 ab
//9 r
//9 10 a,b
//====cur====
//90 ab
//1 r
//10 9 a,b
//====cur====
//[ 1, 90 ]

a>b이어야하는데 a<b이기때문에 

a%b   즉 9%10 이여서 r = 9가 되었다. 

그리고 증감문으로 넘어가서 a = b인 10 이 할당되고  b = r인 9가 할당되었다.

그리고 다음 for loop로 넘어간다. 

조건문에서는 r = 10(a) % 9(b)   즉 r = 1   true이기에  증감문으로 또 넘어간다

그래서 a = 9 (b) , b = 1(r) 이 할당되었고 

다시 증감문으로 넘어가니 r = 9(a) % 1(b) 는 0이기에 false가 되어 for문이 끝난다. 

 

따라서  return [ 1(b), 90(ab)/1(b)] 가되어

최종적으로  [1, 90] 이 출력된다. 

 

대단하다 for문은 활용할 줄이야....