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

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

---

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

문제 설명

---

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

---

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예제

---

• arr	result
  [2,6,8,14]	168
  [1,2,3]	6

코드

---

def gcd(n1, n2):
    if (n1 < n2):
        (n1, n2) = (n2, n1)
    while n2 != 0:
        (n1, n2) = (n2, n1 % n2)
    return n1

def solution(arr):
    answer = arr[0]
    for i in range(len(arr)):
        answer = (answer * arr[i]) / gcd(answer, arr[i])
    return answer

다른 사람 코드

from fractions import gcd

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

    return answer

코드 설명

---

• 내 코드
  • 유클리드 호제법 사용
    • n이 m보다 크면 두 값의 위치를 바꿔줍니다.
    • n2가 0이 아닌동안 유클리도 호제법을 이용해 최대 공약수를 구해줍니다.
    • 최대공약수를 이용해 최소 공배수를 구해줍니다.
  • 유클리드 호제법이란?
    • 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
    • 호제법 == 두 수가 서로 상대방의 수를 나누어 원하는 수를 얻는 알고리즘
    • 2개의 자연수 a b 에 대해서 a를 b로 나눈 나머지가 r이면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
  • 최소공배수 구하는 법
    • (a*b)/최대공약수
• 다른 사람 코드
  • from fractions import gcd 사용해 직접 gcd 구현을 안함