[프로그래머스/Swift] 135807번 - 숫자 카드 나누기

🔗 문제 링크

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

💡 구현 아이디어

1. 철수 카드의 공약수를 구함 - 유클리드 호제법 사용
2. 구한 공약수로 영희 카드의 값을 나눔
3. 나눠지지 않으면 저장(기존의 저장한 값보다 크다면)
4. 영희 카드의 공약수를 구함 - 유클리드 호제법 사용
5. 구한 공약수로 철수 카드의 값을 나눔
6. 나눠지지 않으면 저장(기존의 저장한 값보다 크다면)
7. 결과값 반환

💻 코드

import Foundation

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    let arrayA = arrayA.sorted()
    let arrayB = arrayB.sorted()
    var result: Int = 0 // 결과값
    
    // 공약수를 구함
    let aGcdNum = findGCD(arrayA)
    let aGcds = findCDs(aGcdNum).sorted(by: >)
    let aTemp = comp(arrayB, aGcds)
    
    let bGcdNum = findGCD(arrayB)
    let bGcds = findCDs(bGcdNum).sorted(by: >)
    let bTemp = comp(arrayA, bGcds)
    
    result = max(aTemp, bTemp)
    
    return result
}

// 최대 공약수 구하기
// num1 <= num2
func gcd(_ num1: Int, _ num2: Int) -> Int {
    if num2 % num1 == 0 {
        return num1
    }
    return gcd(num2 % num1, num1)
}

// 배열을 받아서 배열의 최대 공약수를 반환
func findGCD(_ array: [Int]) -> Int{
    if array.count == 1 { return array[0] }
    
    var num: Int = gcd(array[0], array[1])
    if array.count >= 3 {
        for idx in 2..<array.count {
            num = gcd(num,array[idx])
        }
    }
    return num
}

// 숫자를 받아서 숫자의 약수 반환
func findCDs(_ num: Int) -> [Int] {
    var cds: Set<Int> = Set<Int>()
    for i in 1...Int(sqrt(Double(num))) {
        if num % i == 0 {
            cds.insert(i)
            cds.insert(num/i)
        }
    }
    return cds.sorted()
}

// 비교할 배열과 공약수를 입력 받아서 조건에 맞는 최대 양의 정수 반환
func comp(_ origin: [Int], _ gcds: [Int]) -> Int {
    var result: Int = 0
    for gcd in gcds {
        var flag = true
        for number in origin {
            if number % gcd == 0 {
                flag = false 
                break
            }
        }
        
        if flag {
            result = max(result, gcd)
        }
    }
    return result
}

❌ 틀린 이유 및 틀린 부분

⏳ 시간 복잡도

• 최대 공약수의 개수 * 배열의 원소수 = O(M * N)

📌 풀이 또는 기억할 정보