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

문제 링크

문제

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

입출력 예

풀이

최대공약수와 최소공배수를 구하는 문제이다. 둘의 공식은 아래와 같다.

• 최대공약수 : 유클리드 호제법
• 최소공배수 : a * b / 최대공약수

유클리드 호제법이란?
쉽게 설명하자면,
a > b 일 때,
a % b = r (나머지)
b % r = r2
r % r2 = r3
..
..
나머지가 0이 될 때 까지 반복한다.
이 때, 나머지를 0으로 만든 나눈 수가 최대공약수가 된다.

유클리드 호제법의 규칙을 살펴보자면, 나머지가 0이 되기 전까진 나누는 수 / 나머지가 재귀적으로 실행된다. (처음에 b의 위치에 있던 값이 a로 이동됨.)

그럼 찾은 규칙을 이용하여 코드를 구현해보자.

function solution(n, m) {
    var answer = [];
    
    // 최대공약수 함수
    const gcf = (a,b) => {
        if ( b === 0) { // 나머지가 0이 되면 나눈 수를 반환.
            return a
        }
        return gcf(b, a % b) // 나머지가 0이 아니면 재귀로 함수를 실행한다.
    }
    // 최소공배수 함수
    const lcm = (a,b) => (a*b) / gcf(a,b)
    
    return [gcf(n,m), lcm(n,m)];
}

Takeaway

이번 문제는 최대공약수를 구하는 법만 알면 최소공배수까지 쉽게 해결되는 문제였다. 하지만 최대공약수를 알기 위해선 유클리드 호제법을 공부해야했다. 처음엔 살짝 헷갈리는 감이 있었지만, 공식을 계속 써보며 규칙을 찾으니 그 뒤론 쉬운 문제였다.