[파이썬] 프로그래머스 N개의 최소공배수 풀이

문제 확인

프로그래머스

나의 풀이

• N개 수의 최소 공배수를 구하기 위해선, 두 정수 사이 최소 공배수를 구한 다음, 그 최소 공배수와 다음 정수 사이 최소 공배수를 구하면 된다.
  • 기존 최소 공배수가 다른 정수에도 적용 되기 위해선, (최소 공배수 * 상수 배) 형식이어야 하기 때문에
• 각각 최소 공배수를 구하는 과정에서 최악의 경우, 대략 $(100^2)**14$ 정도의 시간 복잡도가 발생하기 때문에, 유클리드 호제법을 활용해 최소 공배수를 찾았다. 
• 유클리드 호제법을 활용한 최소 공배수, 최대 공약수 구하는 방법은 포스팅에서 확인할 수 있다.

# 최대 14번 반복 -> 완전 탐색 시 최악의 경우(100*100)**14의 연산 필요 -> 시간 초과
# 유클리드 호제법 활용
def solution(arr):
    # 유클리드 호제법 사용 위해 정렬
    arr.sort()
    for i in range(1, len(arr)):
        #a, b의 최대 공약수는 b, r의 최대 공약수와 같음
        a, b = arr[i], arr[i - 1]
        # lcm * gcd = a * b 성질 활용
        mul = a * b
        while b != 0:
            r = a % b
            a = b
            b = r
        # 각 성분에 lcm 저장
        arr[i] = mul // a
    return arr[-1]