알고리즘 - freeCodeCamp - Smallest Common Multiple.part3

매일 한 시간씩 3일에 걸쳐서 풀었다. 해결방법은 freeCodeCamp 힌트를 이용했다.
힌트에서 위키백과에 있는 최소공배수를 참고하라고 링크를 해놨다. 최소공배수를 구하려면 최대공약수를 이용한다. 위키백과에서 최대공약수를 참고하니 유클리드 호제법이 있었다. 먼저 두 수가 있으면 가장 큰 수를 작은 수로 나눈다. 나눠서 나온 나머지가 0이 아니면 나누는 수를 나머지로 나눈다. 나머지가 0이 될 때까지 반복한다. 나머지가 0이 될 때 나누는 수가 최대공약수가 된다.

최소공배수는 주어진 두 수를 곱하고 최대 공약수로 나누면 최소공배수가 나오게 된다.

풀이

function smallestCommons(arr) {
  const sortedArr = arr.sort((a, b) => a - b); // 가.

  let leastCommonMultiple = 1; // 나.

  for (let i = sortedArr[0]; i <= sortedArr[1]; i++) { // 다.
    leastCommonMultiple = 
    (leastCommonMultiple * i) 
    / greatestCommonDivisor(leastCommonMultiple, i)
  }

  return leastCommonMultiple;
}

function greatestCommonDivisor(num1, num2) { // 라.
  let remainder = num1 % num2;
  if (!remainder){ // 마.
    return num2;
  } else if (remainder === 1){ // 바.
    return 1;
  } else {
    return greatestCommonDivisor(num2, remainder); // 사.
  }
}

smallestCommons([1, 5]);

가. 매개변수로 들어오는 배열이 큰 수가 0번째로 들어오는 걸 정렬로 작은 수부터 큰 수로 정렬
나. 두 수의 최소공배수가 되는 leastCommonMultiple변수 선언
다. leastCommonMultiple과 i의 곱을 greatestCommonDivisor(유클리드 호제법)의 결과로 나눈 값을 leastCommonMultiple에 할당한다. 주어진 범위까지 반복한다.
라. 최대공약수를 구하는 함수
마. remainder가 0이면 나눈 값인 num2를 반환
바. remainder가 1이면 서로소라고 해서 서로 최대공약수가 1 이외엔 없다. 1를 반환
사. 0, 1의 조건들이 전부 아니었을 때 재귀

느낀점

이번 알고리즘을 풀면서 최대공약수에 대한 코드도 구현해서 좋았다. 그리고 여러번 수정을 했다. 이게 최종본이다. 이전에는 함수 안에 numbers 배열이 하나 더 있었다. 매개변수로 들어온 배열에는 두 수가 있는데 두 수 범위 안에 있는 모든 수를 numbers 배열에 담는다. 반복문을 하나 더 만들어야했다. 해결하긴 했지만 코드를 다시 보니깐 줄일 수도 있겠다는 생각을 했다. numbers 배열에 숫자들을 넣는 과정에서 계산을 하면 반복문을 하나 더 만들지 않아도 될 거 같다는 가정을 했다. 그리고 leastCommonMultiple 변수도 처음에 1이 있는 범위가 있으면 1를 곱하는건 필요하지 않는거 같았다. 1이 포함된 배열이 들어오면 1다음 수과 그 다음 수를 곱해서 leastCommonMutiple에 할당했다. 그렇게 해보니 다른 것도 따로 코딩을 해줘야 했다. 차라리 leastCommonMultiple에 1을 할당하면 다른 코드들을 작성하는게 필요치 않게 된다고 생각하게 됐다. 두 가지 생각을 정리를 잘해서, 적용을 해보니 코드가 훨씬 줄어들었다.

유클리드 호제법 - 최대공약수 구하는 방법: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%9