LV1 18 최대공약수와 최소공배수

문제 설명

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

 

제한 사항

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

 

입출력 예

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

 

나만의 풀이

  우선 최대공약수와 최소공배수는 무조건 1 이상이다. 이유 제한 사항에 있음!! gcd, lcm을 변수로 1을 선언했다. 그 후 반복문과 if문을 이용해 문제를 풀었는데.

  최대공약수는 둘 중 가장 작은 수 까지 반복문을 돌리고 if문으로 n, m의 두 수에 나머지가 0되는 큰 수를 반환하고 최소공배수는 while문을 이용해서 계속 반복하게 하고 lcm을 ++하게 하고 if문에 n, m을 둘 다 나눴을 때 나머지 0이 되는 숫다 있으면 break;를 했다.

  return으로 [gcd, lcm]하면 끝~~

function solution(n, m) {
    let gcd = 1;
    let lcm = 1;
    
    for (let i = 2; i <= Math.min(n, m); i++) {
        if (n % i === 0 && m % i === 0) {
            gcd = i;
        }
    }
    
    while (true) {
        if (lcm % n === 0 && lcm % m === 0) {
            break;
        }
        lcm++;
    }
    
    return [gcd, lcm]
}

  쉽게 구하는 법이 있지 않을까 생각을 해서 검색을 하니 유클리드 호제법이라는 것이 있었다.

  함수를 반복하게 하고 a % b === 0이 되는 수가 최대공약수,

   a * b를 한 후 최대공약수를 나누면 최소공배수가 나오게 된다는 거였다.

  확실히 코드도 간단해지고 런타임도 많이 줄었다는 것을 알 수 있었다~~ 역시 이래서 구글링이 짱인 것 같다~~

function solution(n, m) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    
    return [gcd(n, m), lcm(n, m)];
}