문제 설명 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
🔵 풀이
최소공배수는 두 값의 곱을 최대공약수로 나눈 값이라는 건 알고 있다.
그런데 최대공약수는 어떻게 구하지?!!
1부터 일일이 나눠봐야하나...!!!!
결국 구글의 도움을 빌려, 유클리드 호제법으로 최대공약수를 구할 수 있음을 알게 되었다.
유클리드 호제법 : 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘. 정수 a, b에 대하여 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
=> a를 b로 나눈 나머지 r을 구하고, 다시 b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
유클리드 호제법을 이용한 풀이는 다음과 같다.
func solution(_ n:Int, _ m:Int) -> [Int] {
var divisor = min(n, m)
var dividend = max(n, m)
var rest: Int = dividend % divisor
// 최대공약수 찾기
while rest != 0 {
dividend = divisor
divisor = rest
rest = dividend % divisor
}
let gcd = divisor
// 최소공배수 찾기
let lcm = n * m / gcd
return [gcd, lcm]
}
