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

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

 

코딩 테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

 

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미.

 n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

 

테스트 케이스

 

문제를 접근할 때 필요한 개념은 두 개가 존재

• 최대 공약수 - GCD
• 최소 공배수 - LCM

최대 공약수의 경우 유클리드 호재법으로 계산이 되며 최소 공배수의 경우 다음과 같다.

 

LCM = a * b / GCD ( a, b )

 

즉 최소 공배수를 구하기 위해서는 구하고자 하는 두 수를 곱하고 두 수의 최대 공약수로 나눠주면 된다. 

 

 

최대 공약수 - GCD

 

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

 

코드

 

n개의 수에서 최소 공배수를 구해야하니 n개의 수를 다 곱하고 n-1개의 최대 공약수를 나눠줘야 한다고 생각했다.

이때 n-1개의 최대 공약수는 반복문을 통해서 GCD 메서드를 사용, 그리고 arr1 배열에 넣어줬었다.

def solution(arr):
    answer = 1
    arr1=[]
    arr.sort()
    for i in range(1,len(arr)):
        arr1.append(gcd(arr[i-1],arr[i]))
    for i in arr:
        answer *= i
    for i in arr1 :
        answer//=i
    return answer

 

다만 해당 코드의 경우 테스트 케이스 부분에서는 성공했지만 채점을 하면 실패라는 결과가 나왔어서 다시 방법을 구현했다...

이번에 접근을 한 방법은 아까 위헤서 본 LCM = a * b / GCD ( a, b ) 그 자체로 접근을 하였다.

 

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

 

생각을 해보니 두 수를 먼저 곱해서 최소 공배수를 만들면 결국 다음 수의 경우에도 공배수를 만드는 작업만 진행하면 되었는데 해당 부분에 대해 생각을 못했다. 전체를 한 번에 구하려는 것이 아닌 부분 별로 나눠서 구하는 것이 풀이 과정의 열쇠였다.