최대공약수와 최소공배수 - 프로그래머스 level1

오늘은 프로그래머스 최대공약수와 최소공배수 문제를 풀어보겠습니다.

문제는 다음과 같습니다.

 

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

코딩테스트 연습 - 최대공약수와 최소공배수

 

풀이 방법

- 유클리드 호제법을 이용해서 최대공약수를 구하고,

- 최소공배수는 두 수의 곱을 최대공약수로 나누면 간단하게 문제를 풀 수 있습니다.

 

소스 코드 

- 최대공약수 

   b가 0일 때까지 재귀로 값을 구한 후에 b가 0이면 a를 리턴해줍니다.

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

 

- 최소공배수

  a와 b의 곱을 구한 후 최대공약수로 나누면 구할 수 있습니다.

const lcm = (a,b) => {
    return a * b / gcd(a,b);
}

 

전체 소스 코드는 다음과 같습니다.

 

const gcd = (a,b) => {
    if(b===0)return a;
    return gcd(b, a%b);
}
const lcm = (a,b) => {
    return a * b / gcd(a,b);
}

function solution(n, m) {
    let answer = [];
    answer.push(gcd(n,m));
    answer.push(lcm(n,m));
    return answer;
}