[프로그래머스] level.2 N개의 최소공배수 (*)

https://school.programmers.co.kr/learn/courses/30/lessons/12953#

프로그래머스

 

 

 

나의 풀이 

 

1) reduce 사용

function solution(arr) {
    const gcd = (a,b) =>{
        const remainder = a%b;
        if( remainder === 0) return b;
        return gcd(b, remainder)
    }
    return arr.reduce((a,b) => a*b / gcd(a,b))
}

이 문제의 핵심은 3개를 초과하는 여러 수의 최소공배수를 어떻게 구할 것인가 이다. 

 

나는 처음에 잘못된 접근방식으로 접근했다. 

a , b , c, d가 주어졌을 때   

a, b의 최소공배수 = x       

a,c의 최소공배수  = y

a,d의 최소공배수  = z

를 구한뒤       x*y*z  / ((arr.length - 2) * a)   이렇게 생각했다. 

지금 생각하면 말도 안된다. 

예제 2,6,8,14만 보고 생각했던 것 같다. 

 

핵심은 

a, b, c가 주어졌을 때 

a 와 b의 최소공배수 x  와 c의 최소공배수가   바로 a, b, c의 최소 공배수가 된다. 

 

예를 들어 [3, 4, 5]가 주어졌을 때 

 

3, 4, 5의 최소 공배수는 60이다. 

or

3, 4의 최소 공배수는 12 이다

12, 5의 최소 공배수는 60 이다. 

 

또 다른 예로 [2, 6, 12] 일때

 

2, 6 ,12 의 최소 공배수는 12이다. 

 

2, 6의 최소 공배수는 6이다. 

 

6, 12의 최소 공배수는 12이다. 

 

이때 활용하기 좋은게 바로 reduce이다. 

최소 공배수는 lcm 함수만들면 끝 

문제는 [a,b,c,d .... 등 여러 숫자가 주어졌을때 

a,b의 최소공배수를 다시 lcm함수에 넣고  그와 동시에 c를 넣어주고 

다시 그 결과 값과 d를 lcm함수를 넣어주게 만들어야한다. 

arr.reduce((a,b) =>  a*b / gcd(a,b)) 라고 해주면 된다. 

 

reduce에 초기값을 전달하지 않으면 배열의 첫 번째 요소를 사용한다. ( 단, 빈 배열에서 초기값 없이 reduce를 호출하면 오류가 발생한다.)

예제를 [2, 6, 12]로 하자면 

처음 a는 2이고 b는 6이다. 

그래서 2와 6의 최소공배수 6이  return되면 그게 a = 6으로 다시 할당되어지고    b가 12가 된다.  그리고 다시 이 둘의 최소 공배수값 12가 return 되면 그게 바로 2,6,12의   최소 공배수이다.  

이런식으로 작동하는 것만 이해하면 된다. 

 

++ 추가 

일전에  "영어 끝말잇기" 문제에서 다른 사람풀이에 reduce를 잘 활용 했는데 그와 함께 보는 것이 좋다. 

https://html-jc.tistory.com/434?category=933046 

[프로그래머스] level.2 영어 끝말잇기 (*)

 

2) reduce를 사용 안 한다면 

function solution(arr) {
    const gcd = (a,b) =>{
        const remainder = a%b;
        if( remainder === 0) return b;
        return gcd(b, remainder)
    }
    while (arr.length >= 2){
        let a = arr.pop()
        let b = arr.pop()
        arr.push( a*b / gcd(a,b))
    } 
    return Number(arr)
}

이런식으로 하면 맨 뒤에서 숫자 두 개를 뺀 뒤  최소 공배수를 구하고 다시 뒤에 넣고 

다시 뒤에서 숫자 두 개를 빼면 하나는 이전에 구한 최소공배수 값이고 다른 하나는 기존 숫자이다. 

이런식으로 길이가 1이 될때까지하면 마지막으로 남은 숫자가 전체 숫자의 최소 공배수가 된다.