N개의 최소공배수

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

문제 설명

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

제한 사항

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

입출력 예

풀이

def gcd(num1, num2):
    mod = num1 % num2

    while mod:
        num1 = num2
        num2 = mod
        mod = num1 % num2

    return num2


def lcm(num1, num2):
    return (num1 * num2) // gcd(num1, num2)


def solution(arr):
    answer = arr[0]

    for num in arr[1:]:
        answer = lcm(answer, num)

    return answer

해결 과정

N개의 최소공배수를 구할 때 현실에서는 아마 모든 수를 놓고 최대공약수를 구한다음에 남은 나머지들을 곱하여 구했을 것이다.

하지만, 사실 N개를 한 번에 다 하지 않고, 일부의 최소공배수를 구한 뒤, 다음 수와 또다시 최소공배수를 구해도 상관없다.

예를 들어, [2, 6, 8, 14]의 최소공배수를 구할 때, 다음과 같이 진행할 수 있다.

1. 2와 6의 최소공배수는 6이다.
2. 1에서 구한 최소공배수와 8의 최소공배수는 24다.
3. 2에서 구한 최소공배수와 14의 최소공배수는 168이다.

다른 사람의 풀이

from fractions import gcd


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

    return answer

다음과 같이 gcd 모듈을 가져와 nclm 함수 하나만으로 문제를 해결할 수 있다. 어떤 때는 이렇게 하나의 함수만으로 해결하는 게 좋을 때도 있을까?