[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/12953
📌문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항 )
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
💡 문제 풀이
최대 15개 숫자들의 최소공배수를 구해야하는 문제다.
최소공배수를 구하기 위해서 '소인수 분해'의 개념을 생각하였다.
- 소인수분해 → 공통인 소수 중 지수가 큰 수와 공통이 아닌 소수들의 곱
분해할 수 있는 수의 가장 넓은 범위는 2부터 arr의 최대값이다(arr의 최대값이 소수일 경우).
또한 공통인 소수로 나누었을 때 지수가 큰 수를 곱해야한다.
ex)
8, 30의 최소공배수는 120이다.
8 = 23, 30 = 2 x 3 x 5 로 소인수분해를 하였을 때 공통인 소수 '2'에 관해서는 지수가 가장 큰 23을 곱하여 최소공배수를 만들어나간다.
(이후 공통이 아닌 소수 3, 5를 곱하여 120을 구할 수 있다.)
위 작업은 모든 배열의 수가 소인수 분해로 모두 나누어 떨어져 1이 될 때 까지 반복한다.
즉, 배열의 합 = 배열의 길이 일 때까지 반복!
divide 함수
소수 num으로 나누어 질 때까지 반복하여 나눈다.
더 이상 나누어 떨어지지 않으면 cnt와 n을 return
- cnt : 나눈 회수(=지수)
- n : 나누고 남은 값
- answer : 최소공배수
- num : 소인수분해를 진행할 소수(2부터 max(arr)까지)
1씩 증가하지만 앞에서 소수에 해당하는 수를 나눌 수 있을때 까지 나누기 때문에 소수가 아닌 숫자로 나눠질 일이 없다!
ex) [4, 8, 12]일경우 2로 나누었을 때 [1, 1, 3]이 되므로 이후 num이 4가된다고 해도 나눠지는 일이 없다.
def divide(num, n):
cnt = 0
while True:
if n % num:
return cnt, n
else:
n //= num
cnt += 1
def solution(arr):
answer = 1
num = 2
while sum(arr) != len(arr):
count = 0
for i in range(len(arr)):
if not arr[i] % num:
cnt, res = divide(num, arr[i])
arr[i] = res
count = max(count, cnt)
answer *= (num ** count)
num += 1
return answer파이썬은 참 친절하다... 내장함수 math모듈에서 최소공배수를 구하기 위해 필요한 최대공약수를 구해주는 gcd함수를 지원한다.
from math import gcd
def solution(num):
answer = num[0]
for n in num:
answer = n * answer / gcd(n, answer)
return answer위와 같이 함수를 이용하여 간단한 코드를 작성할 수 있다.
