[백준] (Swift) 2609번 - 최대공약수와 최소공배수

🟠 문제

https://www.acmicpc.net/problem/2609

🟠 나의 풀이

최대공약수와 최소공배수를 구하기 위해서는 소수를 전부 구하고, 소수로 다 나눠주면서 최대공약수를 먼저 구해야하나? 생각했다. 하지만, 이렇게 하면 시간초과가 날 것 같았고, 효율적이지 못하다는 생각이 들었다. 그러다가 생각난게 예전에 한번 접해봤던 gcd라고 불렸던 무슨 알고리즘이 생각났다. 생각난 김에 다시 공부하려고 포스팅을 작성했다.

https://didu-story.tistory.com/357

[알고리즘] (swift) 유클리드 호제법 (feat. 최대공약수, 최소공배수 구하기)

이 글에서 최소공배수와 최대공약수를 구하는 방법이 나와있고, 이 방법을 그대로 사용하여 코드를 작성했다.

🟠 정답 코드

private func solution() {
    var nm = readLine()!.split(separator: " ").map { Int($0)! }
    let gcd = gcd(nm[0], nm[1])
    let lcd = (nm[0] * nm[1]) / gcd
    print(gcd)
    print(lcd)
}

private func gcd(_ n: Int, _ m: Int) -> Int {
    return m == 0 ? n : gcd(m, n%m)
}

solution()