코딩테스트 연습 04: [프로그래머스] 최대공약수와 최소공배수

출처 : 프로그래머스
사용 언어 : JavaScript

초기 코드

function solution(n, m) {
    var answer = [];
    return answer;
}

내가 작성한 코드

function solution(n, m) {
    var answer = [];
    if(n<m){
        if(m%n!==0){
            answer[0]=1;
            answer[1]=n*m;
        }else{
          answer[0]=n;
          answer[1]=m;  
        }
    }else if(m<n){
        if(n%m!==0){
            answer[0]=1;
            answer[1]=n*m;
        }
        else{
            answer[0]=m;
            answer[1]=n; 
        }

    }else if(n=m){
        answer[0]=n;
        answer[1]=n; 
    }
    
    return answer;
}

최대 공약수가 1이 아니라면 n,m의 나머지가 0일거라는 착각으로 짠 코드,,,ㅠㅠ

테스트해보니 최대 공약수는 1이 아니지만 나머지도 0이 아닌 많은 수 조합들이 있었다....
예시 결과만 보고 무지성으로 짠 코드 였다...하하하...

검색해보니 최소공배수를 구하는 쉬운 방법 유클리드 호제법이 있었다!오호...!?

유클리드 호제법은 MOD연산을 반복하면 된다고 한다.
(MOD연산 : 두 값을 나눈 나머지 구하기)

1230과 904의 최대공약수 구하기 !

• 1230은 904로 나누어떨어지지 않기 때문에, 1230을 904로 나눈 나머지를 구한다. => 326
• 904는 326로 나누어떨어지지 않기 때문에, 904를 326로 나눈 나머지를 구한다. => 252
• 326는 252로 나누어떨어지지 않기 때문에, 326를 252로 나눈 나머지를 구한다. => 74
• 252는 74로 나누어떨어지지 않기 때문에, 252를 74로 나눈 나머지를 구한다. => 30
• 74는 30으로 나누어떨어지지 않기 때문에, 74를 30으로 나눈 나머지를 구한다. => 14
• 30은 14로 나누어떨어지지 않기 때문에, 30을 14로 나눈 나머지를 구한다. => 2
• 14는 2로 나누어떨어진다
  
  따라서, 최대공약수는 2
  
  최대공약수를 구하는 코드~!

function solution(a, b){
    while (b > 0)
    {
        let tmp = a;
        a = b;
        b = tmp%b;
    }
    return a;
}

참고 블로그 : 링크텍스트

최대공약수는 최소공배수를 아니까 쉽게 구할 수 있다!
두 수를 곱한 다음 최대공약수로 나눠주면 된다!
=> A x B = 최대공약수 X 최소공배수 이므로 🙂

다시 작성한 코드

function solution(n, m) {
    var answer = [];
    let a=n;
    let b=m;
     while (m > 0){
        let tmp = n;
        n = m;
        m = tmp%m;
    }
    answer[0]=n;
    answer[1]=(a*b)/n
    
    return answer;
}

ㅠㅠ

다른 사람 풀이

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

wow....

🙍 📝

for문이 이렇게도 쓰일 수 있나 싶었다...
댓글 설명을 보니,
T/F 조건을 (r=a%b) 로 판별하고 0이 나오면 for문이 종료되게 된다고 한다.
그렇구나,,,배우쟈 배우쟈!