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

문제 링크

문제풀이:

주어진 arr = [2,6,8,14]의 최소 공배수를 찾아 반환하는 문제.

1. 모든 수들의 최소 공배수라는 것은 모든 원소들끼리의 최소 공배수를 구하면 된다는 의미

2. 2와 6의 최소공배수(= r)를 구하고 r과 8의 최소공배수를 구한다.

3. 위의 과정을 반복, 배열 내의 모든 원소들과 연산하여 최소공배수를 찾는다.

핵심:

1. 두 수(a,b)의 최소 공배수 연산 구현
   -> 두 수(a,b)의 최소 공배수 = a*b/최대 공약수
2. 최대 공약수 연산 구현
   -> 유클리드 호제법 이용 (링크달자)
3. 모든 원소들을 앞에서 부터 차례대로 계산 후, 연산한 결과를 가지고 다음 원소와 또다시 연산해야 하므로 파이썬의 reduce모듈 이용해서 구현

코드 구현

from functools import reduce

def solution(arr):
    return reduce(lambda a,b: lcm(a,b),arr)
    
# 최대 공약수 계산
def gcd(a,b):
	while b > 0:
    	a,b = b, a%b
    return a
# 최소 공배수 계산

def lcm(a,b):
	return a*b/gcd(a,b)