두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항 두 수는 1 이상 1000000 이하의 자연수입니다.
풀이
class Solution {
fun solution(n: Int, m: Int): IntArray {
val gcd = gcd(n, m)
return intArrayOf(gcd, lcm(n, m, gcd))
}
private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
private fun lcm(a: Int, b: Int, gcd: Int): Int = a * b / gcd
}
말 그대로 최대 공약수와 최소공배수를 구하는 방식입니다. 이러한 문제를 푸는 방법은 두 가지가 있습니다. 일일이 값들을 하나씩 줄여가면서 최대 공약수인지 확인하고 최소공배수의 경우 큰 값을 곱해가면서 일일이 확인하는 방법입니다. 그렇지만 이 방법은 시간도 오래 걸립니다. 그때 우리는 gcd와 lcm을 유클리드 호제법이라는 알고리즘을 이용하여 쉽게 풀 수 있습니다.
여기서 유클리드 호재법이란 2개의 자연수에서 최대 공약수를 구하는 공식으로 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
이것을 보면 알다시피 b와 a% b의 공약수 a의 최대 공약수와 같습니다. 그렇다면 a% b , (a% b)% b, b의 최대 공약수는 같습니다 그렇다면 a와의 최대공약수도 같다는 말입니다. 이렇게 해나 갔을 때 an% bn 이 0이라면 이때 bn의 값이 최대공약수라는 것이 이 알고리즘이 말하는 바입니다. 이러한 방법은 a% b로 값이 하나씩 줄어드는 것보다 빨리 줄어들어 기존에 사용하던 1씩 내리는 방법보다 더욱 빠르게 최대 공약수를 구할 수 있습니다. 유크리드 호제법을 더 자세히 알고 싶다면 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
최소 공배수의 경우 a = bq+ r -> gcd*α = a , gcd*β = b -> gcd*α*β = 최소 공배수 = a*b/gcd 이게 성립되므로 쉽게 최소 공배수를 구할수 있습니다
