[Programmers] 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

나의 문제 풀이

function solution(n, m) {
    let answer = [];
    let min = n > m ? m : n;
    let max = n > m ? n : m;
    let multiply = max * min;
    
    while (min > 0) {
        let temp = 0;
        
        if (max % min === 0){
            answer.push(min);
            break;
            
        } else {
            temp = max;
            max = min;
            min = temp % min;
        }
    }
    
    answer.push(multiply / answer[0]);
    
    return answer;
}

• 주어진 두 수 중에서 큰 수와 작은 수를 판별하여 각 변수에 할당한다.
• 큰 수와 작은 수를 곱한 값을 미리 변수에 할당한다.
• 큰 수가 작은 수로 나누어 떨어지는 경우 작은 수는 두 수의 최대공약수이기 때문에 정답 배열의 요소로 넣고 반복문을 빠져나온다.
• 아닐 경우 큰 수에 작은 수를 넣고, 작은 수에 큰 수를 작은 수로 나눈 나머지를 넣는다.
  • 이때 원본 값을 유지하기 위해 임시 변수가 필요하다.
• 만약 작은 수가 0보다 크다면 위 과정을 반복하며 최대공약수를 구한다.
• 반복문을 빠져나와 큰 수와 작은 수를 곱한 값을 최대공약수로 나누어 구한 최소공배수를 정답 배열의 요소로 넣고 리턴한다.

---

다른 사람의 문제 풀이

function gcdlcm(a, b) {
    var r;
    for (var ab= a * b; r = a % b; a = b, b = r) {}
    return [b, ab / 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)];
}

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

 

 

😱