두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
arr | result |
---|---|
[2,6,8,14] | 168 |
[1, 2, 3] | 6 |
//[n1.n2,n3] -> [n1과n2의 최소공배수, n3]
func solution(_ arr:[Int]) -> Int {
var data: [Int] = arr
while data.count > 1 {
if data[0] < data[1] {
data.swapAt(0,1)
}
var lcm = data[0] * data[1] / gcd(data[0],data[1])
data.removeSubrange(0..<2)
data.append(lcm)
}
return data[0]
}
func gcd(_ p: Int, _ q: Int) -> Int{
if q == 0 {
return p
}
return gcd(q,p%q)
}
아래 글은 코드가
왜
최소공배수와 최대 공배수를 구할 수 있는지 설명하는 글이다. 이유가 궁금하지 않다면 단순히 코드만 보는 것을 추천한다.
이번 문제는 N 개의 수에서 최소공배수를 구해야 한다. 우선 일반적인 경우인 두 개의 수에서 최소 공배수를 구하는 방법을 생각해 보자. 소인수 분해를 사용하는 방법이 있지만 다른 방법은 수1 * 수2 / 최대공약수
의 식을 이용하는 방법이다. 위 식의 증명방법을 보고 싶다면 최소공배수 구하는 방법
을 검색하거나 또는 소인수 분해를 생각하면 확인할 수 있을 것이다.
우리는 이제 2개의 수에서 최소 공배수를 구하는 방법을 알았다.(그렇다고 가정하자ㅋ). 이를 N 개(3개)인 경우로 확장한다. [n1, n2, n3]
세 개의 수에서 최소공배수를 구하기 위해 우선 n1
과 n2
의 최소공배수를 구한다. 이를 lcm1
이라고 하자. 이제 이 lcm1
와 n3
의 최소공배수를 lcm2
라고 하자. lcm2
는 세 개의 수의 최소 공배수가 된다.
위의 사실이 이해가 안 가거나 수학적으로 확인하고 싶다면 소인수 분해를 생각해 보자. 예를 들어 3,10,24
의 수가 있다. 이들을 소인수 분해로 표현하면 3(3), 10(2*5), 24(2^3*3)
으로 표현된다. 최소 공배수는 이 세 개의 수의 소인수들에서 가장 큰 지수를 가진 소인수들의 곱으로 구할 수 있다. 위 경우에서는 2^3 * 3 * 5 = 120
이 된다. 이 결과를 보면 3개의 소인수들을 한 번에 곱하여 계산한 것을 확인할 수 있다.
그러나 2개의 수 3(3), 10(2*5)=>30
을 먼저 계산하고 계산한 결과와 나머지 1개의 수인 30(2*3*5), 24(2^3*3)=>120
와 계산해도 결과는 120
으로 같기 때문에 우리는 N개의 수를 2개씩 분할하여 N 개의 최소 공배수를 얻을 수 있다는 최종 결론을 얻는다. 그리고 계산 순서도 관계가 없다는 사실을 알 수 있다.
되게 말이 길었다.. 짧게 표현하고 싶었으나 다른 풀이들을 찾아봐도 제출한 코드들이 최소공배수를 얻는 원리에 대해서 기술한 글이 없길래 혹시나 궁금한 사람을 위해 최대한 설명을 하였다.
최대 공약수를 구하는 메소드 gcd
는 유클리드 알고리즘을 사용한다.
다음으로 N 개의 최소공배수를 구하는 과정이다.
var data: [Int] = arr
while data.count > 1 {
if data[0] < data[1] {
data.swapAt(0,1)
}
var lcm = data[0] * data[1] / gcd(data[0],data[1])
data.removeSubrange(0..<2)
data.append(lcm)
}
로직은 간단하다. 입력으로 들어온 배열의 앞쪽의 2개의 원소의 최소공배수를 구한다. 두 원소의 최소공배수를 구하면 이를 배열의 제일 끝에 추가한다. 그리고 최소 공배수를 구하는 데 사용된 수는 제거한다. 이를 배열의 원소가 1개 남을 때까지 반복하면 N 개의 수에서 최소공배수를 구할 수 있다.
해당 방법은 단순한 방법이다. 물론 단순하고, 효율성이 매우 떨어지지만 이런 방법이 있다 정도로 참고하면 좋다고 생각하여 기술한다. 해당 방법은 주어진 배열에서 가장 큰 수에서 시작하여 1씩 증가하여 최소 공배수를 확인하는 방법이다.
코드는 다음과 같다.
var num = arr.max()!
while true{
if arr.count == arr.filter{num % $0==0}.count {
break
}
num += 1
}
단순히 1씩 증가한 값이 입력으로 주어진 배열에서 모든 원소에 대해 나누어떨어지는 경우 그 수는 최소공배수가 된다. 그러나 해당 방법은 효율적이지 못하다. 이는 실행 결과를 통해 확인할 수 있다.