코딩테스트 Python 알고리즘 (N개의 최소공배수)

문제

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨

프로그래머스

 

 

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

 

 

---

코드

gcd는 최소공배수를 구하는 함수이다.

 

a * b // gcd (a,b)는 a와 b의 최소공배수를 나타내는 식이다.

 

 

풀어보자면 arr에는 숫자가 n개 만큼 있을것이다.

for 루프를 통하여 n-1번만큼 반복하게 한다.

 

arr의 시작또한 0부터 이기 때문에 

위의 식에서 a = arr[i]가 될것이며, b = arr[i+1]이 될 것이다.

 

반복을 하게 된다면 arr[i+1]은 두번째 반복에는 arr[i]가 되기 때문에 값을 최소공배수로

변환을 시켜줘야 한다.

 

이렇게 arr의 끝까지 최소공배수를 구해준다면 

i+1은 반복한 횟수가 되고

arr[i+1]은 최소공배수가 된다.

from math import gcd
def solution(arr):
    for i in range (0,len(arr)-1):
        arr[i+1] = arr[i] * arr[i+1] // gcd(arr[i], arr[i+1])
    return arr[i+1]

 

 

---

링크

Programmers/프로그래머스/2/12953. N개의 최소공배수 at main · K-MarkLee/Programmers

Programmers/프로그래머스/2/12953. N개의 최소공배수 at main · K-MarkLee/Programmers