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

 

 

 

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

프로그래머스

 

문제요약

• n개의 숫자를 담은 배열이 주어졌을 때, 원소들의 최소 공배수를 반환하여라
• 배열의 길이는 1 이상, 15 이하이다.
• 배열의 원소는 100 이하의 자연수이다.

 

첫 번째로 접근한 방식은, 배열에 속한 숫자들 중 제일 큰 수의 배수를 구하고 해당 값이 나머지 숫자들로 나누어 떨어지는지 확인했다. 아래는 이 방식을 자바스크립트로 작성한 코드이다.

 

 

풀이과정

function solution(arr) {
    let answer = 0;
    // maxN: 배열의 원소중 제일 큰 수 / x: maxNum에 곱할 값
    let maxN = Math.max(...arr), x = 1;
    
    while(answer === 0) {
        for (let i=0; i < arr.length; i++) {
            // maxN의 배수가 나누어떨어지지 않을 경우 x+1.
            if(maxN * x % arr[i] !== 0) {
                x++;
                break;
            // maxN의 배수가 모든 원소로 나누어떨어진경우, answer에 maxN의 배수를 할당.
            } else if(i === arr.length - 1) {
                answer =  maxN * x;
            }  
        };
    };
    
    return answer;
}

 

다른 사람들은 어떻게 풀었나 살펴보니 다수가 유클리드 알고리즘을 사용해서 최대 공약수를 구하고 이를 활용해 최소공배수를 구하는 방식으로 해결했다. (A와 B의 최대공약수를 C라고 했을 때, A와 B의 최소공배수는 A*B/C이다)

유클리드 알고리즘: 최대 공약수를 구할 때 사용하는 알고리즘
1. 두 자연수 A, B가 있다고 가정했을 때
2. A%B = C
3. C가 0이면 B는 A의 최대 공약수이다.
4. C가 0이 아니면 A자리에 B, B자리에 C를 대입(B%C)해 나머지가 0이 될 때까지 반복한다.

 

이 공식을 파이썬으로 풀어낸 코드는 아래와 같다.

 

풀이과정

from functools import reduce

def solution(arr):
    lcm =reduce(get_lcm, arr)
    return int(lcm)
    
# 최대공약수 구하는 함수
def get_gcd(a,b):
    x, y = max([a,b]), min([a,b])
    while y != 0:
        x,y = y, x % y
    return x

# 최소공배수 구하는 함수
def get_lcm(a,b):
    return a*b / get_gcd(a,b)

 

 

 

 

---

참고 자료

• https://blockdmask.tistory.com/53