[프로그래머스] 숫자 카드 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/135807

✍️ 첫번째 접근

예전에 풀다가 시간 초과로 인해 해결하지 못한 문제인데 그때 당시에 접근은 이랬다.

• 철수의 카드 배열에 해당하는 모든 원소를 접근하면서 각 원소의 약수를 구한다.
• 이미 등장했던 약수라면 해당 약수의 개수를 count하면서 Dictionary에 저장한다.
• 이때, 대칭성을 이용해 1부터 제곱근까지의 범위를 적용하여 약수를 구할 수 있다.
• 마찬가지로 영희도 같은 논리를 적용한다.

이렇게 접근하였는데 각 원소에 해당하는 모든 약수를 구하다보니 시간 초과가 발생하였다.

import Foundation

func divisor(_ arr: [Int], _ d: inout [Int:Int])  {
    for i in arr {
        let end = Int(sqrt(Double(i)))
        for j in 1...end {
            if i % j == 0 {
                if d[j] == nil {
                    d.updateValue(1, forKey: j)
                }
                else {
                    d[j]! += 1
                }
                if d[i/j] == nil {
                    d.updateValue(1, forKey: i/j)
                }
                else {
                    d[i/j]! += 1
                }
            }
        }
    }
}


func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    let n = arrayA.count
    var d1: [Int:Int] = [:]
    var d2: [Int:Int] = [:]
    divisor(arrayA, &d1)
    divisor(arrayB, &d2)
    for i in d1 {
        if i.value == n && !d2.keys.contains(i.key) {
            return i.key
        }
    }
    for i in d2 {
        if i.value == n && !d1.keys.contains(i.key) {
            return i.key
        }
    }
    
    return 0
}

✍️ 두번째 접근

카드 배열에 있는 모든 원소의 약수를 구하지 말고, 카드 배열에 있는 모든 원소의 최대공약수를 구하는 방식으로 접근하여 해결하였다.
문제에서 가장 큰 양의 정수를 구한다고 하였으니 최대공약수를 구하는 것이 적합하다고 생각했기 때문.

import Foundation

// 최대공약수
func GCD(_ min: Int, _ max: Int) -> Int {
    let res = min % max
    if res == 0 {
        return max
    }
    return GCD(max,res)
}

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    // 최대공약수를 구하기 위해 수를 정렬
    let arr1 = arrayA.sorted{$0 < $1}   // 철수
    let arr2 = arrayB.sorted{$0 < $1}   // 영희
    let n = arr1.count
    if n == 1 { // 크기가 1이라면
        if arr1.first! == arr2.first! { // 중복된 원소일 수 있으므로
            return 0
        }        
        return arr1.first! > arr2.first! ? arr1.first! : arr2.first!    // 가장 큰 수를 리턴
    }
    // 각 배열의 최대공약수를 구함
    var gcd1 = GCD(arr1[0],arr1[1])
    var gcd2 = GCD(arr2[0],arr2[1])
    for i in 2..<n {
        gcd1 = GCD(gcd1,arr1[i])
        gcd2 = GCD(gcd2,arr2[i])
    }
    let cnt1 = arr2.filter{$0 % gcd1 == 0}.count    // 철수의 최대공약수가 영희의 카드 중에서 나눌 수 있는 개수
    let cnt2 = arr1.filter{$0 % gcd2 == 0}.count    // 영희의 최대공약수가 철수의 카드 중에서 나눌 수 있는 개수
    if cnt1 == 0 && cnt2 == 0 { // 주어진 조건을 만족하는 가장 최대공약수를 리턴
        return max(gcd1,gcd2)
    }
    if cnt1 == 0 {
        return gcd1
    }
    if cnt2 == 0 {
        return gcd2
    }
    
    return 0
}