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

문제 설명

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

제한 사항

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

입출력 예arrresult

[2,6,8,14]	168
[1,2,3]	6

---

 

문제를 풀기전, 최소공배수를 구하는 방법에 대해 알아보자.

 

간단한 예로 최소공배수를 구해보자.

def ex_gcd(a, b): 	# a=18, b=24라고 가정
    A = a
    B = b
    while b > 0:
        a , b = b, a % b
    gcd = a 	# 최대공약수
    return A*B // gcd

위의 예시는 최소공배수를 구하는 문제이다. 18과 24의 최소공배수를 구해보자.

밑의 그림과 같이 구하면 되고, 최소공배수는? 2*3*3*4를 해서 72가 나올 것이다.

또 하나, 최대공약수는 6이 나올 것이다.

 

규칙을 찾았는가?

바로 최소공배수는 최소공배수를 구할 두 수를 서로 곱하여 최대공약수로 나누면 최소공배수가 된다는 것이다.

즉, 18 과 24를 서로 곱하여 나온 수를 최대공약수(6)로 나누면 최소공배수(72)가 나온다.

18과 24의 최소공배수

---

본 문제에 대한 나의 풀이

def solution(arr):
    from math import gcd                           
    answer = arr[0]                                 
    for num in arr:                                
        answer = answer*num // gcd(answer, num)     
    return answer

1.  최대공약수를 구하는 gcd() 함수를 import 한다. ((gcd() 함수는 두 수의 최대공약수를 구해주는 함수))

2. answer을 arr[0]으로 초기화

3. 반복문을 처음부터 끝까지 돈다.

4. arr[0], arr[1])의 최소공배수를 구한 후 answer에 저장

5. 4번에서 구한 최소공배수, arr[2])의 최소공배수를 구한 후 answer에 저장

6. 모든 배열을 돌면서 최소공배수를 구하고, 저장하고 하는 방식을 진행 ((최소공배수 = (x*y) / gcd(x,y))

 

정리하자면 이렇다.

• 최소공배수를 계속해서 answer에 저장시켜 answer와 arr[index]를 통해 계속해서 최소공배수를 구해야 함
• gcd() 함수는 두 수의 최대공약수를 구해주는 함수
• // 연산자는 몫만 구하는 연산자