[Node.js_4기] 코드카타 : n개의 최소 공배수 (24/03/07)

목차

 

1. 문제

2. 시도

3. 결과

4. 배운점

 

1. 문제 

 

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr)

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

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

 

2. 시도 

 

유클리드 호제법 을 이용하는 문제이다.

(2개의 자연수 a, b (a > b)에 대해서 a를 b로 나눈 나머지 ( = a % b)를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.)

// 최대 공약수
const gcd = (a,b) => {
    while(b>0){
        let temp = b;
        b = a%b;
        a = temp
    }
    return a
};
// 최소 공배수
const lcm = (a,b) => {
    return (a*b)/gcd(a,b)
};

function solution(arr) {
    let answer = 1
    for(let i = 0;i<arr.length;i++){
        answer = lcm(answer,arr[i])
    }
    return answer;
}

 

3. 결과 

테스트 1 〉	통과 (0.06ms, 33.4MB)
테스트 2 〉	통과 (0.06ms, 33.5MB)
테스트 3 〉	통과 (0.06ms, 33.4MB)
테스트 4 〉	통과 (0.05ms, 33.4MB)
테스트 5 〉	통과 (0.05ms, 33.4MB)
테스트 6 〉	통과 (0.05ms, 33.4MB)
테스트 7 〉	통과 (0.06ms, 33.4MB)
테스트 8 〉	통과 (0.06ms, 33.4MB)
테스트 9 〉	통과 (0.06ms, 33.4MB)
테스트 10 〉	통과 (0.13ms, 33.5MB)

 

4. 배운점 

 

20분정도 for문만 사용해서 풀려고 삽질을 하다가 

이전에도 비슷한 문제를 풀었던 기억이 나서 깃허브를 뒤져 찾아내었다. 

코딩테스트 연습 - 최대공약수와 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr)

당시에는 두 수의 최대공약수와 최소공배수를 구하면 되었지만, 위에서는 배열 내의 모든 수에 대해 적용해야 했기 때문에 나온 최소 공배수를 answer에 할당하고 다음순서로 넘어가길 반복하는 것으로 응용했다.