문제 풀이 아이디어

공약수를 통해서 푸는 문제입니다. 먼저 배열 A와 배열 B의 모든 수를 나눌 수 있는 가장 큰 수, 즉 최대 공약수를 구해야 합니다. 그리고 나서 해당 최대공약수가 다른 배열의 수를 모두 나눌 수 있는지 확인해야 합니다.

서로의 배열을 나누는 여부를 “최대 공약수”만으로 확인해도 되는 이유

처음에 문제를 읽으면 배열 A이 최대공약수만이 아니라 “모든 약수”로 배열 B를 나누면서 확인해야 하는 것이 아닌가라고 생각할 수 있습니다. 하지만 “최대공약수”만 확인하면 됩니다. 어떤 이유인지 단계별로 설명을 해보겠습니다.

1. 배열A의 최대공약수를 gcdA라고 합시다.
2. gcdA가 배열B의 어떤 수 b를 나눌 수 있었습니다. 따라서 gcdA는 답이 아니었습니다.
3. 그래서 gcdA 다음으로 큰 배열A의 공약수 cdA를 가지고 배열B를 나누고자 합니다.
4. 이런 경우 b를 cdA가 나눌 수 있을까요? 없을까요?

공약수 cdA는 무조건 최대공약수 gcdA의 약수입니다. 따라서 gcdA로 나누어지는 b는 무조건 cdA로도 나누어질 수 밖에 없습니다. 따라서 최대공약수 gcdA로 나누어지는 수가 배열B에 있다면 모든 배열A의 약수들은 정답이 될 수 없습니다.

배열의 최대공약수 구하기

자 그러면 이제 배열의 최대공약수 2개를 구하고 서로의 배열의 모든 수를 나누어보면 됩니다.

최대공약수 구하는 함수는 이 포스팅을 참고해주세요

A, B, C 세 자연수의 최대공약수를 구하기 위해서는 A와 B의 최대공약수를 먼저 구한 뒤 (A와 B의 최대공약수)와 C의 최대공약수를 구하면 됩니다. 이렇게 구한 수는 A, B, C 공통된 최대공약수가 됩니다.

마찬가지로 배열의 경우도 순서대로 둘 씩 짝지어서 최대공약수를 구하면 됩니다. 고차함수 reduce 사용해서 구현하면 아래와 같습니다.

// gcd는 최대 공약수를 구하는 함수
let gcd = array.reduce(array[0]) { gcd($0, $1) }

코드

// 최대 공약수를 구하는 함수
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

// 최대공약수가 다른 배열을 나눌 수 있으면 최대공약수를, 없으면 0을 리턴하는 함수
func getAns(_ gcd: Int, _ array: [Int]) -> Int {
    for num in array {
        if num % gcd == 0 { return 0 }
    }
    return gcd
}

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {

    let gcdA = arrayA.reduce(arrayA[0]) { gcd($0, $1) }
    let gcdB = arrayB.reduce(arrayB[0]) { gcd($0, $1) }

    return max(getAns(gcdA, arrayB), getAns(gcdB, arrayA))
}