Posts
프로그래머스1분

프로그래머스 | #Lv1 "최대공약수와 최소공배수"

목차6

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 조건

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

나의 풀이

코드
function solution(n, m) {
  let answer = [];
  const greatest = (a, b) => {
    if (b === 0) return a;
    return greatest(b, a % b);
  };
  const least = (a, b) => (a * b) / greatest(a, b);
  return [greatest(n, m), least(n, m)];
}

다른 풀이

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

마무리

유클리드 호제법에 대해 배운 문제였다.

최대 공약수는 유클리드 호제법으로 풀이하고, 최소 공배수는 주어진 자연수 2개를 곱하고 최대 공약수로 나누는 방식으로 구한다.

코드
 const greatest = (a, b) => {
    if (b === 0) return a;
    return greatest(b, a % b);
  };

최대공약수는 b가 0이면 a를 반환도록 하고 재귀함수를 사용해서 나머지가 0이 될때까지 진행한다.

코드
const least = (a, b) => (a * b) / greatest(a, b);

최소공배수는 주어진 자연수 2개를 곱하고 최대공약수로 나누어 구한다.

코드
return [greatest(n, m), least(n, m)];

배열에 담아 리턴한다.

다른사람의 풀이는 true/false 조건을 (r=a%b) 로 판별하고, 0이 나오면 for문이 종료되게 했다. 많이 배운다.

Reference

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기

반응형