2lv N개의 최소공배수

문제로 이동
프로그래머스 2단계 N개의 최소공배수 문제풀이입니다.
문제를 봐도봐도 이해가 안된다 싶을 때 보러와주세요.

문제 해결 원리

유클리드호제법을 이용해 최대공약수 -> 최소공배수를 구해 최소공배수까리 최대공약수 -> 최소공배수를 구해 마지막 남은 최대공약수를 알아냄으로 문제를 해결했습니다.

문제 해결 방법

유클리드 호제법에서 최대공약수와 최소공배수를 구하는 공식은 다음과 같습니다.

유클리드 호제법

최대공약수 :

1. 큰 수 % 작은 수

나머지가 0이 되면 작은 수가 최대공약수입니다.

2. 작은 수 = 큰 수 % 작은 수, 큰 수 = 작은 수 

위의 나머지가 0이 아니라면 2번의 연산을 수행합니다.
바뀐 큰 수와 작은 수를 다시 1번 과정을 통해 나머지가 0인지를 확인하고 아닌경우 2 -> 1번 과정을 반복합니다.


예시를 들어보겠습니다.
6과 8이 있습니다. 큰 수는 8 작은 수는 6입니다.

8%6 //결과는 2

나머지가 0이 아니므로 다음 연산을 수행합니다.

작은 수 = 8%6 = 2, 큰 수 = 6

다시 나머지가 0이 나오는지 비교합니다.

6%2 //결과는 0

나머지가 0이므로 최대공약수는 2입니다.

최소공배수 :

1. 큰 수 * 작은 수 / 최대공약수 

최소공배수는 최대공약수만 안다면 간단하게 알아낼 수 있습니다.


예시를 들어보겠습니다.
6과 8이 있습니다. 최대공약수는 2 였습니다.

6 * 8 / 2 //결과는 24

최소공배수는 24입니다.

자세한 문제 해결

위 내용을 바탕으로 문제를 해결하는데 문제가 발생합니다. 이문제는 2개의 최소공배수를 구하는 것이 아닌 여러개의 최소공배수를 구하는 것입니다.

알고있는 위 정보를 바탕으로 문제를 해결하려면 배열의 요소를 2개씩 묶어 연산을 수행합니다.

 for (let i = 0; i < arr.length; i += 2) {
    ... 생략 ...
      }
    }

요소를 2개씩 묶기위해 for문을 이용합니다. index를 2씩 더하는 이유는 한번의 반복에서 i와 i+1을 비교하기 때문입니다.
이때 배열의 요소가 짝수라면 큰 문제가 없지만 홀수의 경우 마지막 요소와 undefined가 묶이게 됩니다. 이를 방지하기위해

 if (i === arr.length - 1) { //i가 마지막 요소일 때, 짝수일경우 이 경우가 발생하지 않는다.
        continue;
      } 

조건을 줘서 마지막 요소는 최소공배수를 구하는 연산을 하지않고 넘어가게 했습니다.

이제 최대공약수를 구하는 공식을 만들어봅시다.
최대공약수는 따로 함수를 만들어 좀더 직관적으로 보기 쉽게 만들었습니다.

function 최대(작은값, 큰값) {
  let 작은값보관소;
  while (작은값 != 0) {
    작은값보관소 = 작은값;
    작은값 = 큰값 % 작은값;
    큰값 = 작은값보관소;
  }
  return 큰값;
}
.... 중략 ....
let 최대공약수 = 최대(작은값, 큰값);

작은값보관소라는 변수를 주고 그안에 매개변수로 전달받은 작은 값을 대입한 이유는

작은값 = 큰값 % 작은값;

이 부분에서 작은 값이라는 변수에는 나머지가 들어가기 때문입니다. 큰 값에는 나머지가 아닌 이전의 작은 값이 들어가야하기에 따로 변수로 만들어 저장했습니다.

이제 최대공약수를 바탕으로 최소공배수를 구하고 구하기 위해 쓰여진 큰 값 작은 값을 지우고 최소공배수를 넣어줍니다.

 let 최소공배수 = (작은값 * 큰값) / 최대공약수;
        arr.splice(i, 2, 최소공배수);

여기까지 하게된다면 전체 배열이 순회하며 큰 값 작은 값을 연산하여 최소공배수가 만들어지고 배열의 크기는 절반으로 줄게됩니다.

[큰값,작은값,큰값,작은값,큰값,작은값,큰값,작은값] 이었다면
[최소공배수, 최소공배수, 최소공배수, 최소공배수]가 되게됩니다. 

최소공배수를 다시 큰 값, 작은 값으로 생각하고 반복하게 된다면 배열의 크기는 절반씩 줄며 최종적으론 1이되게 됩니다.

 while (arr.length !== 1) {
... 최소공배수 반복....
      }
    }
  }

while문으로 배열의 크기가 1이 될때까지 위 과정을 반복하면 N개의 최소공배수를 도출해낼 수 있게됩니다.

🧑🏻‍💻 전체코드

function 최대(작은값, 큰값) {
  let 작은값보관소;
  while (작은값 != 0) {
    작은값보관소 = 작은값;
    작은값 = 큰값 % 작은값;
    큰값 = 작은값보관소;
  }
  return 큰값;
}

function solution(arr) {
  while (arr.length !== 1) {
    for (let i = 0; i < arr.length; i += 2) {
      if (i === arr.length - 1) {
        continue;
      } else {
        let [작은값, 큰값] = [arr[i], arr[i + 1]].sort((a, b) => a - b);
        let 최대공약수 = 최대(작은값, 큰값);
        let 최소공배수 = (작은값 * 큰값) / 최대공약수;
        arr.splice(i, 2, 최소공배수);
      }
    }
  }
  return arr[0];
}

🧑🏻‍💻 문제 푼 후기
이전 1단계에서 두 수의 최소공배수를 구하는 문제를 푼 적이 있습니다. 그때는 유클리드 호제법을 몰라 실패했었고 검색하며 찾아낸 공식이 유클리드 호제법이었습니다. 그걸 기억해내 이문제에 응용해 쉽게 해결한 것 같습니다. 비록 코드가 길고 부족한 점이 많지만 앞으로 발전해나갈 건데 뭐 어떻습니까.

엘리트 코드 분석

아래의 코드는 프로그래머스 해당문제의 좋아요수가 가장 많은 사람의 코드입니다.

function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

제 긴 코드를 6줄로 압축시키다니 세상엔 고수들이 많은 것 같습니다.
더욱 발전하기 위해 잘짜여진 코드를 분석해보겠습니다.

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

최대공약수를 도출해내는 코드입니다.
첫번째 a%b는 재귀함수의 종료 조건이자 참일시 gcd(b,a%b)를 수행합니다. 이또한 마찬가지로 유클리드 호제법을 기반으로 작성되었습니다.
자세히 살펴보면 gcd(b, a % b)로 순서를 바꿔 원래 a자리에 b가오며 b자리에 a%b의 값이 옵니다. 다시 함수 자신을 이 값으로 불러오게되며
a%b -> 순서바꾸고 나머지 대입을 반복하다보면 언젠가 a%b가 0이 되는 시점이 오게되고 a%b가 false가 되어 최대공약수 b가 반환되게됩니다.

function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}

최소공배수를 도출해내는 코드입니다.
ab / gcd(a,b)에서 gcd(a,b)는 최대공약수 b로 반환되었으므로
ab/최대공약수가 됩니다. 이것 자체가 최소공배수가 되었고 reduce 함수에의해 최소공배수는 a로 배열의 다음차례의 수를 b로해서 위과정을 끝까지 반복하는 것입니다.