[프로그래머스/JS] 최대공약수와 최소공배수

문제

 

나의 코드

function solution(n, m) {
    var answer = [];
    
    for(let i = 1; i <= n; i++)
        {
            if(n % i == 0 && m % i == 0)
                {
                    answer[0] = i;
                }
        }
    
    answer[1] = n * m / answer[0];
    
    return answer;
}

 

풀이

우선 최소 공약수를 구하는 식으로 for문을 돌려 n까지 돌린다. n 과 m중 어디든 상관 없다. 이제보니 코드로 둘중 작은 곳을 찾아서 했으면 더 좋았을 것 같다. for문을 n까지 돌리는 중 i로 두 수를 나눴을 때 동시에 0이 되는 수는 약수이다. 그것을 계속 넣다보면 최대 n까지 갔을 경우 answer[0]의 값이 최대 공약수이다. 최소 공배수의 경우 좀 더 쉬웠는데 최소 공배수의 식은 해당하는 (n * m / 최대 공약수)를 하면 쉽게 최소 공배수를 구할 수 있다.

 

다른 사람의 풀이

function gcdlcm(a, b) {
  var gcd = calc_gcd(a, b);
  var lcm = (a * b) / gcd;

    return [gcd, lcm];
}

function calc_gcd(a, b) {
  if (b == 0) return a;
    return a > b ? calc_gcd(b, a % b) : calc_gcd(a, b % a);
}

유클리드 호제법을 사용하여 풀었다. 유클리드 호재법의 경우 

- a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)
- 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다
- 서로가 나누어지면 a%b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.

를 기반으로 계속 나누다 보면 최대 공약수를 구할 수 있다는 풀이 법이다.

위의 풀이 방법은 유클리드 호제법을 이용하여 재귀함수를 사용하여 b가 0이 아닐경우 계속 해당 식을 돌려서 계산하였다.

최소공배수인 lcm의 경우 위의 설명하였듯이 a * b / gcd(최대 공약수) 의 방법으로 구하였다.