[프로그래머스 Level 1] 최대공약수와 최소공배수 (자바스크립트)

Description

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

Constraints

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

 

 

유클리드 호제법(-互除法, Euclidean algorithm)

이 문제를 풀기 위해서는 유클리드 호제법이라는 것에 대한 개념을 알아야 한다. 그래서 개념을 좀 짚고 넘어가려고 한다. 출처는 위키백과.

 

유클리드 호제법이란, 2개의 자연수 혹은 정식(整式)의 최대공약수를 구하는 알고리즘이다. 

 

'호제'는 무슨 뜻일까?

두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는다는 것이다. 

 

어떤 방식으로 최대공약수를 구할까?

a > b이고 a % b === r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다 
b % r === r1
r % r1 === r2 ... (나머지가 0이 될 때까지반복)

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

 

 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

 

예를 들어 24와 10의 최대공약수를 구해 보자.

24 % 10 === 4 
10 % 4 === 2
4 % 2 === 0

여기서 마지막에 나누는 수는 2이고, 2가 24와 10의 최대공약수이다. 

 

---

 

최대공약수를 위와 같은 방법으로 구했다면, 최소공배수는 쉽게 구할 수 있다.

바로 두 수를 곱한 후, 최대공약수로 나눠주면 된다.

 

 

My Solution

function solution(a, b) {
  return [gcd(a, b), lcm(a, b)];
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

function gcd(a, b) {
  if (b === 0) return a;
  return a > b ? gcd(b, a % b) : gcd(a, b % a);
}

 

나는 최대공약수를 구하는 함수, 최소공배수를 구하는 함수를 각각 따로 만들었다.

 

최대공약수를 구할 때, 유클리드 호제법의 원리를 이용해 a가 b보다 크면 gcd 함수에 인자로 b와 a % b를 전달하였다.

이를 반복하여 b가 0이 되면, a를 리턴하게 되고 그것이 바로 최대공약수이다.

 

재귀함수를 이용해서 코드가 심플해질 수 있었다.

 

Other's Solution

function greatestCommonDivisor(a, b) {
  return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);
}
function leastCommonMultipleOfTwo(a, b) {
  return (a * b) / greatestCommonDivisor(a, b);
}
function gcdlcm(a, b) {
  return [greatestCommonDivisor(a, b), leastCommonMultipleOfTwo(a, b)];
}

최대공약수를 구하는 방법이 비슷하면서도 약간 다르게 한 풀이이다.

b가 true일 때, 즉 0이 아니라면 자기 자신을 호출해 인자로 b, a % b를 넘겨 준다.

b가 false일 때는 Math.abs(a)를 리턴하는데, 문제가 개편되기 전이라 이 부분이 약간 다르다.

현재 개편된 문제에서는 a를 그냥 리턴해도 정답이다.

 

function solution(a, b) {
  var r;
  for (var ab = a * b; (r = a % b); a = b, b = r) {}
  return [b, ab / b];
}

이런 for문은 처음 보았다. 조건을 저렇게 쓰고, 중괄호를 아예 비어있게 하는 헝식.

아직 이 풀이법은 정확하게 해석이 되지 않는다.

 

function gcdlcm(a, b) {
  var gcd = function (b, a) {
    var r = b % a;
    return r ? gcd(a, r) : a;
  };
  return [gcd(b, a), (b * a) / gcd(b, a)];
}

위 풀이는 나머지를 변수 r로 지정해서 좀 더 직관적으로 이해할 수 있는 풀이라고 생각한다.