[Programmers] 최대공약수와 최소공배수(JavaScript)

 

알림

 

본 포스팅은 공부 목적으로 작성된 글이며 상업적 목적으로 절대 사용되지 않았음을 밝힙니다.

 

문제

 

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

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

 

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

 

코드(정확성 테스트 불통과)

 

function solution(n, m) {
    let answer = [];
    m % n === 0 ? answer.push(n, m) : answer.push(1, n*m)
    return answer;
}

 

 

단순하게 m을 n으로 나눴을 때, 나머지가 0이면(나눠지면) 최대공약수는 n, 최소공배수 m, 그게 아니면 최대공약수는 1, 최소공배수는 n*m으로 접근했습니다.

 

테스트 1, 2만 보고 하드코딩(?)한 결과라 그런지 1, 2번은 통과했지만, 그 외에 정확성 테스트에서는 통과하지 못했고, 최대공약수와 최소공배수를 구하는 공식이 있나 알아보고 다시 접근해 봤습니다.

 

코드(정확성 테스트 통과)

 

function solution(n, m) {
    let G = (a, b) => b === 0 ? a : G(b, a % b)
    let L = (a, b) => a * b / G(a, b)
    return [G(n, m), L(n, m)];
}

 

우선 이 문제에선 최대공약수와 최소공배수를 구하는 공식도 알아야 하고, 유클리드 호제법이란 알고리즘도 적용시켜서 풀어야 합니다.

 

유클리드 호제법이란 최대공약수를 구하는 알고리즘인데요. a와 b에 대해서 나눈 후, 0이 나올 때까지 나머지로 계속 나눠주는 방법입니다.

 

1. 최대공약수 구하기

 

따라서 최대공약수를 구할 땐 유클리드 호제법을 사용해, b가 0이 되면 a를 return을 하고, 아니면 될 때까지 계속 b를 a와 b의 나머지로 나눠주도록 합니다.

 

2. 최소공배수 구하기

 

최소공배수를 구하는 공식은 아래의 공식을 이용해 구해야 합니다.

 

최대공약수 * 최소공배수 = a * b
따라서, 최소공배수 = (a * b) / 최대공약수

 

따라서 최소공배수를 구하려면 a와 b를 곱한 뒤 사전에 구한 최대공약수로 나눠주면 됩니다.