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

문제 정보

제목 : N개의 최소공배수

난이도 : Lv.2

사용 언어 : Python

문제 링크

https://school.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

 

---

나의 풀이

수학적 지식이 필요했던 문제였습니다.  문제를 해결하기 위해 2개의 함수를 정의했습니다. 유클리드 호제법을 이욯해 A B의 최대공약수를 구합니다. 최소공배수 = A * B / 최대공약수라는 관계를 이용하여 최소공배수를 구하는 함수를 정의했습니다. 함수를 정의한후 arr의 길이가 2이상일 동안 반복하는 while문을 생성하여 a와 b에 arr.pop()를 이용해 각각 값을 저장하고 arr에 a와 b의 최소공배수를 구한 값을 추가해줍니다.

arr의 길이가 1이 남을경우 answer에 arr[0]을 저장하여 리턴합니다.

 

 

유클리드 호제법
2개의 자연수a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

코드를 예시로 들자면 a%b가 0이 아니라면 a에는 b를 b에는 a와 b를 나눈 나머지를 저장합니다. 반복하다가 a를 b로 나눈 나머지가 0이 된다면 나누는 수인 b를 리턴합니다.

def gcd(a,b) :
    while True :
        if (a%b == 0) :
            return b
        else :
            a,b=b,a%b

최소공배수와 최대공약수의 관계

A = 10, B = 12를 예시로 한다면

A = 2 * 5

B = 2 * 2 * 3

A와 B의 최대 공약수는 2(2), 최소 공배수는 60(2*2*3*5)입니다.

A와 B를 곱하게된다면

A * B = 2 * 5 * 2 * 2 * 3 이렇게 되고 이는 A * B = 최대공약수 * 최소공배수가 됩니다.

따라서 최소공배수 = A * B / 최대공약수가 성립하게됩니다.

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

 

코드

def gcd(a,b) :
    while True :
        if (a%b == 0) :
            return b
        else :
            a,b=b,a%b

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

def solution(arr):
    while (len(arr) >=2):
        a = arr.pop()
        b = arr.pop()
        arr.append(lcm(a,b))
    
    answer = arr[0]
        
    return answer