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

문제 설명

배열을 입력받고 배열 속 모든 숫자의 최소공배수를 구하는 문제입니다.

작동 방식

두 수의 최소공배수를 구하는 방법은 두 수의 곱을 최대공약수로 나누는 것입니다. 이를 이용하여서 두 수의 최소공배수를 구한 뒤 그 최소공배수와 다른 숫자들의 최소공배수를 구해나가면 이 문제를 해결할 수 있습니다.
코드에서 반복문을 수행하며 순서대로 이전 숫자까지의 최소공배수와 현재 숫자의 최대공약수를 구한 뒤 그를 이용해 처음 숫자부터 현재 숫자까지의 최소공배수를 구하고 모든 연산이 끝난 뒤에 계산된 최소공배수를 출력해줍니다. 이는 위에서 설명한 방식을 그대로 코드로 옮겨놓은 것입니다.

소스코드

def solution(arr):
    lcm = 1

    for i in range(len(arr)):
        gcd = getGCD(lcm, arr[i])
        lcm = (arr[i] // gcd) * lcm

    return lcm


def getGCD(A, B):
    if A < B:
        A, B = B, A

    while A % B != 0:
        temp = A % B
        A, B = B, temp

    return B