코딩테스트 연습 - N개의 최소공배수

처음 풀이: 완전탐색 🚫

처음에는 완전탐색을 활용해서 arr의 최댓값에서 1씩 늘려가면서 arr 안에 모든 수와 나누어 떨어지는 가장 작은 수를 구했습니다. 문제를 풀기는 풀었지만 실행시간이 꽤 길게 걸리는 케이스들이 있었습니다.

사실 이 문제를 이렇게 푸는 것이 아니라 최대공약수와 최소공배수의 정의를 활용해야 합니다.

func solution(_ arr:[Int]) -> Int {

    func isLCM(_ lcm: Int) -> Bool {
        for n in arr {
            if lcm % n != 0 { return false }
        }
        return true
    }

    var lcm = arr.max()!

    while !isLCM(lcm) {
        lcm += 1
    }

    return lcm
}

최대공약수와 최소공배수

위 문제를 풀기 위해서는 최소공배수를 구하는 방법을 알아야 합니다. 그리고 최소공배수를 구하기 위해서는 최대공약수를 활용해야 합니다. 따라서 각각 최대공약수와 최소공배수를 구하는 방법을 알아봅니다.

최대공약수 구하기

최대공약수를 구할 때는 재귀함수를 활용합니다. a와 b의 최대 공약수를 구할 때는 a를 b로 나눈 나머지가 0이 될 때까지 반복하면 됩니다. 나머지가 0일 때는 a를 리턴하고 나머지가 0이 아니라면 b를 a로 나머지를 b로 해서 다시 재귀함수를 실행합니다.

func gcd(_ a: Int, _ b: Int) -> Int {
	// 나머지가 0인 경우 a를 리턴
    if b == 0 {
        return a
	// 0이 아니라면 다시 나누기해서 재귀함수 실행
    } else {
        return gcd(b, a % b)
    }
}

최소공배수 구하기

최소공배수를 구할 때는 최대공배수의 정의를 활용하면 됩니다. (a와 b의 최소공배수) = a * b / (a와 b의 최대공약수)입니다.

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

N개의 최소공배수 구하기

문제 풀이 아이디어

이제 위 공식들을 활용해서 n개의 자연수의 최소공배수를 구하면 됩니다. 자연수 3개 a, b, c가 있다고 가정을 할 때 a, b, c의 최소공배수는 (a와 b의 최소공배수)와 c의 최소공배수와 같습니다. 자연수가 3개 이상일 때도 마찬가지입니다.

고차함수 reduce를 활용하면 코드를 더 간결하게 만들 수 있습니다. 초기값을 1로 한 이유는 1과 a의 최소공배수는 a이기 때문에 향후 연산에 영향을 미치지 않기 때문입니다.

코드

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

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

func solution(_ arr:[Int]) -> Int {
    return arr.reduce(1) { lcm($0, $1) }
}

참고한 블로그 🙏

프로그래머스 N개의 최소공배수 Swift

프로그래머스 최대공약수와 최소공배수 Swift

Swift - 최대공약수 (GCD)