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 이하인 자연수입니다.
- 유클리드 호제법
2개의 자연수(또는 정수) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
class Solution {
private int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
public int solution(int[] arr) {
int result = 1;
for (int i = 0; i < arr.length; i++)
result = arr[i] * result / gcd(arr[i], result);
return result;
}
}
from math import gcd
def solution(arr):
answer = arr[0]
# 두 수의 곱을 두 수의 최대 공약수로 나누면 최소 공배수
for a in arr[1:]:
answer = (answer * a) // gcd(answer, a)
return answer
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
def solution(arr):
# a가 b보다 크게 넣어줘야 하므로 먼저 정렬해주기
arr.sort()
arr.reverse()
answer = arr[0]
for i in range(1, len(arr)):
answer = (answer * arr[i]) // gcd(answer, arr[i])
return answer