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

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

---

나의 풀이

• range(2, n+1)를 이용하여 n의 약수를 구한다 (재귀함수 사용)
• 2, 6, 8 , 14의 약수는 각각 2, 2x3, 2x2x2, 2x7 일 때, 각 숫자가 가지고 있는 약수를 포함하게 만든다
  • 위의 경우 2x2x2x3x7이 최소공배수다

from collections import defaultdict

def getLem(n):
    for i in range(2, n+1):
        if n == i:
            return [i]
        elif n % i == 0 :
            return [i] + getLem(n//i)
    return 0

def solution(arr):
    if 1 in arr:
        arr.remove(1)
    num = defaultdict(int)
    answer = 1

    for a in arr:
        share = getLem(a)
        share_set = set(share)
        for i in share_set:
            if share.count(i) > num[i]:
                num[i] = share.count(i)
    
    for k, v in zip(num.keys(), num.values()):
        answer *= k**v

    return answer

 

---

다른 사람의 풀이

• 최대공약수를 구해주는 gcd를 사용함 
• n와 answer을 곱하고 최대공약수로 나누어주어 최소한의 약수를 갖게 한다

from fractions import gcd


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

    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(nlcm([2,6,8,14]));