[프로그래머스] N개의 최소공배수

출처: https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

 

 

문제 설명

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

 

나의 풀이

function solution(arr) {
    var answer = 0;
    
    let max = Math.max(...arr); 
    let temptemp =Array.from({length: max+1}, () => 0);
    for(let i = 0; i<arr.length; i++){ 
        let x=arr[i]; 
        let temp =Array.from({length: arr[i]+1}, () => 0);
        for(let j = 2; j<=x;){ 
            if(x==j){ 
                temp[j]++; 
                break;
            }
            if(x%j==0){ 
                temp[j]++;
                x/=j; 
            }else{ 
                j++; 
            }
        }
        for(let k=2; k<=arr[i];k++){ 
            if(temp[k]>=temptemp[k]) temptemp[k] = temp[k]; 
        }
    }
    
    answer =1; 
    for(let i=2; i<temptemp.length; i++){ 
        if(temptemp[i]!=0){ 
            for(let j=0; j<temptemp[i]; j++){ 
                answer*=i
            }
        }
    }
    
    return answer;
}

한번에 풀긴 했는데 다른 사람 풀이를 보니까 뭔가 좀... 내 공부방향이 틀린 거 같다 ㅡㅡ;;

---

다른사람풀이

function solution(arr) {
    var gcd = (a, b) => (b % a === 0) ? a : gcd(b % a, a);
    var lcm = (a, b) => a * b / gcd(a, b);
    var nlcm = n => n.sort().reduce((a, b) => lcm(a, b));
    
        return nlcm(arr);
    }

3줄;; 

 

function solution(arr) {
        function gcd(a,b){  //유클리드 호제법을 이용한 최대공약수 구하기 .
        	if(b%a==0) return a; 
        	else return gcd(b%a,a); 
    	}

    function lcm(a,b){ // 최소공배수 구하기. 
        return a*b/gcd(a,b); 
    }

    function nlcm(n){ 
        n=n.sort(); //이부분은 gcd에서 첫번째 인자가 두번째 인자보다 작아야하기 떄문인듯? 
        
        return n.reduce((a,b)=>lcm(a,b));
	}

    return nlcm(arr);
}

아직 화살표 함수 보기가 좀 불편해서 다시 정리해보면 

 

gcd 는 유클리드 호제법으로 최대공약수를 구하고. 

lcm은 두 수를 곱하고 최대공약수로 나눠서 최소공배수를 구하고. 

nlcm은 우선 정렬을 하는데, 최대 공약수를 구할 때 큰 수가 뒤에 와야돼서 그런거 같다. 

그다음에 reduce로 누산한다. 

 

 

---

소감 

유클리드 호제법으로 최대공약수를 구하는 것도 알고,

a와 b의 최소공배수는 a와 b를 곱한 값을 최소공약수로 나눈 몫이라는 것도 알고 있고. 

두개씩 묶어서 최소공배수를 만들어 나가면 된다는 것도 알고 이거로 풀면된다고 생각했는데, 

손 가는대로 코딩하다보니까 처음에 생각했던대로 안 풀고 그냥 막 풀었다. 

 

다음부터는 천천히 다 생각하고 풀어야겠다.