N개의 최소공배수

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다.

 

정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

제한사항 

· arr은 길이 1이상, 15이하인 배열입니다.

· arr의 원소는 100이하인 자연수입니다. 

 

입출력 예

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

---

풀이

1. Me

def gcd(a,b):
    if a < b:
        a, b = b, a 
    return b if a % b == 0 else gcd(b, a % b)

def lcm(a, b):
    return int(a * b / gcd(a,b))

def mul_lcm(arr):
    if len(arr) < 2:
        return arr[0]    
    
    tmp = []
    for a, b in zip(arr, arr[1:]):
        tmp.append(lcm(a,b))
    return mul_lcm(tmp)
    
def solution(arr):
    return mul_lcm(arr)

이전에 배운 최소공배수와 최대공약수 문제를 응용하여 풀었다. mul_lcm이라는 함수를 정의하고, 입력받은 배열을 순차적으로 탐색

하며 두 원소들의 최소공배수를 구하여 새로운 리스트에 추가해주었다. 이 작업을 입력받은 배열의 길이가 1이하가 될 때 까지 반복 

 

2. Others

from fractions import gcd 

def nlcm(num):      
    answer = num[0]
    for n in num:
        answer = n * answer / gcd(n, answer)

    return answer

배열을 순차적으로 탐색하며 최소공배수를 바로바로 구하였다.