[Programmers] N개의 최소공배수

N개의 최소공배수

N개의 최소공배수 를 클릭하면 바로 이동한다.

---

분명히 비효율적 일 것이라는 건 알았지만 우선 바로 생각나는대로 풀어보았다.

1 부터 수를 올려가며 그 수의 약수가 N개의 수에 모두 있으면 반환했다.

def solution(nums):
    check = 1
    for cur in nums:
        check *= cur

    for i in range(1, check):
        div_cnt = 0
        for j in nums:
            if i % j == 0:
                div_cnt += 1
        if div_cnt == len(nums):
            return i

    return check

예상한 대로 답은 맞지만 5000ms 가 나오는 경우도 있다.

아주아주 비효율적 !!

수학적 개념을 이용해 보자. GCD(a, b) * LCM(a, b) = a * b 이다. 그렇다면 LCM = a * b / GCD(a, b) 가 성립한다.

from math import gcd


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

    return answer

물론 이 개념을 알았더라면 당장 이 방법으로 풀었을 것 이다. 하지만.. 수학을 대하는 센스가 부족한 것 같다..

---

GCD 를 구하는 방법을 정리해보자면 유클리드 호제법을 사용하면 된다.

파이썬은 swap 이 간단해서 아주 편하다.

def gcd(a, b):
	while b != 0:
		tmp = a % b
    a, b = b, tmp
    
	return a