[Programmers/JS] N개의 최소공배수 / 프로그래머스 코딩 테스트 연습

N개의 최소공배수

---

문제 설명

 

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

---

예시

arr	result
[2,6,8,14]	168
[1,2,3]	6

---

코드 해석 및 전체 코드

 

1. reduce 함수를 사용하여 최소 공배수 구하기

2. 인덱스 0, 1의 최소 공배수 L 구하기

3. L과 인덱스 3의 최소 공배수 구하기

4. 배열 끝까지 반복

 

예시 1의 배열은 2, 6, 8, 14로 총 4가지의 숫자로 구성되어 있다. 

reduce()를 통해 유클리드 호제법을 이용하여 구한 최소 공배수를 결과값으로 반환한다. 

마지막으로 반환된 최소 공배수가 배열에 담긴 수들의 최소 공배수가 된다. 

 

reduce() 매개변수 a는 누적값인데, 

reduce()를 최초로 호출할 때 첫번째 매개변수는 인덱스 0의 요소 값임 (reduce() 설명은 코드 해석 밑에서 설명함)

 

reduce() 매개변수 b는 처리할 현재 요소를 타나냄

a, b	reducer (최소공배수)	reduce 반환 값
2, 6	2 * 6 / 2	6
6, 8	6 * 8 / 2	24
24, 14	24 * 14 / 2	168

 

function solution(arr) {
    return arr.reduce((a, b) =>{
        return a * b / getGCD(a, b);
    })
}

//최대 공약수를 구하는 함수
function getGCD(a, b){
    if(a % b == 0) return b;
    return getGCD(b, a % b);
}

---

reduce()

reduce 함수는 배열의 각 요소에 reducer 함수를 실행하고 하나의 값을 반환한다.

 

accumulator  콜백의 반환값을 누적하는 변수

currentValue  처리할 현재 요소 

currentIndex  처리할 현재 요소의 인덱스

array  reduce()를 호출한 배열

[0, 1, 2, 3, 4].reduce(function(accumulator, currentValue, currentIndex, array) {
  return accumulator + currentValue;
});

 

유클리드 호제법

2개의 수의 최대 공약수를 구하는 알고리즘

 

a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구함

나머지가 0이 될 때까지 나눈 수가 최대 공약수의 수

 

코드는 위의 최대공약수를 구하는 코드

---

github

programmers