백준 2609번 최대공약수와 최소공배수 Swift

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

2609번: 최대공약수와 최소공배수

내 코드

// 유클리드 호제법
func gcd(_ a: Int, _ b: Int) -> Int {
    var a = a
    var b = b
    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return a
}

func lcm(_ a: Int, _ b: Int, gcd: Int) -> Int {
    return (a * b / gcd)
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

let gcdResult = gcd(N, M)
let lcmResult = lcm(N, M, gcd: gcdResult)

print(gcdResult)
print(lcmResult)

 

---

Review

 

최대공약수(Greatest Common Divisor)를 구할 때
처음에는 아래와 같은 코드로 구했습니다.

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

let minData = min(N, M)

var gcd = 0

for i in (1...minData).reversed() {
    if N % i == 0 && M % i == 0 {
        print(i)
        gcd = i
        break
    }
}

let lcm = (N*M) / gcd
print(lcm)

둘 중에 작은 값을 기준으로 그로부터 1까지 for 문을 돌면서
처음으로 둘 다 나누어 떨어지는 수가 최대공약수라고 생각했고
주어진 두 개의 수를 곱하여 최대공약수를 나누면
최소 공배수가 된다고 생각했습니다.

 

위 코드를 함수로 묶어 내면 아래와 같습니다.

func gcd(_ a: Int, _ b: Int) -> Int {
    let minData = min(a, b)
    
    for i in (1...minData).reversed() {
        if a % i == 0 && b % i == 0 {
            return i
        }
    }
    return 1
}

func lcm(_ a: Int, _ b: Int, gcd: Int) -> Int {
    return (a * b / gcd)
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

let gcdResult = gcd(N, M)
let lcmResult = lcm(N, M, gcd: gcdResult)

print(gcdResult)
print(lcmResult)

하지만 이 경우는 for 문으로 모든 경우를 돌아봐야 되기 때문에 큰 수의 경우 오래 걸릴 수 있습니다.

 

---

 

따라서 최대 공약수 구하는 함수를
유클리드 호제법으로 작성하면
아래와 같은 gcd(Greatest Common Divisor) 함수로 만들 수 있습니다.

func gcd(_ a: Int, _ b: Int) -> Int {
    var a = a
    var b = b
    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return a
}

 

유클리드 호제법은 아래 링크에서 참고해서 볼 수 있습니다.

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