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

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

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 1 중 최대공약수와 최소공배수 문제를 JavaScript를 사용하여 문제를 풀어보도록 하겠습니다.

 

문제 설명

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

 

제한 사항

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

 

입출력 예

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

 

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

 

작성한 답

solution.js

function solution(n, m) {
    var g = gcd(n,m);
    return [g, n*m/g];
}

var gcd=(a, b)=>a%b == 0 ? b : gcd(b,a%b);

 

설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성하는 문제입니다.

최대공약수와 최소공배수를 쉽고 빠르게 구할 수 있는 방법만 알면 위와 같이 아주 간단한 코드로 문제를 바로 해결하실 수 있습니다.

방법을 먼저 알려드리자면 최대공약수는 유클리드 호제법을 사용하여 구하고,

최소공배수는 두 수의 곱 나누기 최대공약수로 구하실 수 있습니다.

 

위키피디아의 설명을 빌려 유클리드 호제법을 설명 해드리자면,

2개의 수 n과 m이 있을 때, n에 m을 나눈 나머지가 r이면 n과 m의 최대공약수는 m과 r의 최대공약수와 같다. 그러므로 m을 r로 나눈 나머지 r'을 구하고, 또 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 n과 m의 최대 공약수 입니다.

 

그러므로 이 과정을 코드로 풀어내면 위에 작성한 gcd() 함수와 같습니다.

인자로 받은 a와 b를 나눈 나머지가 0이면 b를 최대공약수로 반환하고, 그렇지 않으면 재귀 방식으로 b에 a와 b를 나눈 나머지를 다시 나누어 나머지를 구하는 과정을 계속 반복해서 진행합니다.

그렇게하여 유클리드 호제법을 사용하여 최대공약수를 구하고나면, 앞서 말씀 드렸듯이 최소공배수는 두 수의 곱 나누기 최대공약수 이므로,

n * m / g(유클리드 호제법으로 구한 최대공약수) 로 아주 쉽게 바로 최소공배수를 구하실 수 있습니다.

이제 최대공약수와 최소공배수를 모두 구했으므로 두 숫자를 배열로 return 해주시기만 하면 문제를 해결하실 수 있습니다.

 

 

제가 틀린 부분이 있다거나 더 좋은 방법을 아시는 분이 계시다면 댓글로 공유 부탁드립니다!

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청 사항은 언제든지 말씀 해주세요!

 

감사합니다.