[코딩 문제 풀이(파이썬/Python)] 프로그래머스 _ N개의 최소공배수

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

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

[문제 설명]

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

 

[제한 조건]

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

# 다 같아질 때까지 작은 수에 한 번씩 더하기
def solution(arr):
    original = arr.copy()
    while len(set(arr)) != 1:
        arr[arr.index(min(arr))] = arr[arr.index(min(arr))] + original[arr.index(min(arr))]
    return arr[0]

모든 수들에 대해 이전 수와의 최대공약수를 이용해 최소공배수를 구하는 것을 반복하는 방법도 있었다.

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

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

    return answer

유클리드 호제법을 기억해두면 쉽게 활용할 수 있겠다.