[프로그래머스/Programmers] N개의 최소공배수 - Python

Link

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

 

Solution

해당 문제는 arr가 오름차순으로 정렬되어 주어지기 때문에 arr[0]과 arr[1]의 최소공배수를 구하고 구한 최소공배수와 arr[2]의 최소공배수를 구하고 이런식으로 진행하여 모든 수의 최소공배수를 구하는 방식으로 진행하였다.

for문에서 최대한 시간복잡도를 줄이기 위해 arr[i]부터 answer * arr[i] + 1까지 arr[i]의 간격으로 진행하여 최소공배수를 구하였다.

ex) arr[i] == 6, answer == 2 -> range(6, 12 + 1, 6)

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

    for i in range(1, len(arr)):
        for j in range(arr[i], answer * arr[i] + 1, arr[i]):
            if j % answer == 0 and j % arr[i] == 0:
                answer = j
                break

    return answer

🔑 key point: range(arr[i], answer * arr[i] + 1, arr[i])

 

Other Solution

Other Solution에서는 두 수의 최대공약수를 반환하는 math.gcd()를 활용하여 최소공배수를 구하는 방식을 활용하였다.

from math import gcd


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

    for n in arr:
        answer = n * answer / gcd(n, answer)

    return answer

🔑 key point: math.gcd
📌 Tip: n * m / 최대공약수 == 최소공배수