3월 26일 TIL

프로그래머스 코딩테스트 [ 숫자 카드 나누기 ]

Github

• 이 문제는 아래와 같은 양수를 찾는 것이다.

  1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
  2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

• 일단 원소의 길이는 최대 500,000이라서 시간초과가 당연히 문제가 될줄 알았지만, 무작정 풀어봤다.

1번 방법 (내가 풀었던 방법)

• 나는 각각 배열의 모든 요소의 약수를 찾아서 dictionary에 저장을 하고, 각각 약수의 등장횟수를 찾아서, 각 배열의 최대 공약수를 찾았다. 그리고 최대공약수를 다른 배열에서는 나눠지지 않는지 확인을 하였다.
• 로직은 맞지만, 모든 약수를 찾고, 다시 Filter를 사용해서 최대공약수를 찾는 과정에서 시간 초과가 뜬것 같다.

import Foundation

 func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
     var arrA = arrayA.sorted(by: > )
     var arrB = arrayB.sorted(by: > )
     var dicA : [Int: Int] = [:]
     var dicB : [Int: Int] = [:]
     var ans = 0
     for i in 0..<arrA.count{
         let firstDivisors = find(arrA[i])
         let secondDivisors = find(arrB[i])
         for (_, element) in firstDivisors.enumerated(){
             if dicA[element] == nil {
                 dicA.updateValue(1, forKey: element)
             }else{
                 dicA.updateValue(dicA[element]!+1, forKey: element)
             }
         }
         for (_, element) in secondDivisors.enumerated(){
             if dicB[element] == nil {
                 dicB.updateValue(1, forKey: element)
             }else{
                 dicB.updateValue(dicB[element]!+1, forKey: element)
             }
         }
     }
     var dicAFilter = dicA.filter({$0.value == arrA.count})
     var dicBFilter = dicB.filter({$0.value == arrB.count})
     if dicAFilter.count != 0 {
         for (key,value) in dicAFilter{
             if dicB[key] == nil {
                 ans = max(key,ans)
             }
         }
     }
     if dicBFilter.count != 0 {
         for (key,value) in dicBFilter{
             if dicA[key] == nil {
                 ans = max(key,ans)
             }
         }
     }
     
     return ans
 }

 func find(_ n :Int ) -> [Int]{
     var nums : [Int] = []
     let sqrtN = Int(Double(n).squareRoot())
     for i in 1...sqrtN {
         if n % i == 0 {
             nums.append(i)
             if n / i != i {
                 nums.append(n/i)
             }
         }
     }
     nums.remove(at: 0)
     return nums
 }

2번 방법 (allSatisfy 사용해서 바로 찾기)

• 1번 방법은 무식하게 풀었다면, 이번 방법은 주어진 배열의 공약수들을 찾고, 해당 공약수가 다른 배열에서는 약수가 아닌 것들만 저장해서, 그중에서 제일 큰 약수를 반환하는 방법으로 진행했다.
• 이 방법도 역시나 시간초과가 떳다. 아마도 결국은 모든 배열을 돌아야한다는 문제 때문인것 같다.

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    var temp = findCommonDivisors(arrayA, arrayB) + findCommonDivisors(arrayB,arrayA)
    var ans = temp.count == 0 ? 0 : temp.max()!
    return ans
}

func findCommonDivisors(_ numbers: [Int], _ another: [Int]) -> [Int] {
    let minNumber = numbers.min() ?? 0
    var commonDivisors: [Int] = []
    for divisor in 1...minNumber {
        if numbers.allSatisfy({ $0 % divisor == 0 }) && another.allSatisfy({$0 % divisor != 0}){
            commonDivisors.append(divisor)
        }
    }

    return commonDivisors
}

3번 방법 ( 참고블로그 brick님 )

• 이 방법도 GCD를 사용하는거이긴 하지만 약간 다른점은, 두번쨰 방법은 각 배열에서의 제일 작은 숫자를 기준으로, 1부터 해당 숫자까지 다 돌아서 확인하는 것지만, 이 방법은 유클리드 알고리즘을 통해 재귀함수를 통해 GCD를 찾는다.
• 그리고 arr.reduce를 사용해서 현재까지 찾은 최대공약수를 다음숫자와 비교하는 방식으로, 각 배열에서 최대공약수 하나만을 찾을수 있다.

func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    
    let gcdA = gcd(arrayA)
    let gcdB = gcd(arrayB)
    let answerA = arrayB.allSatisfy { gcdA != 1 && $0 % gcdA != 0 } ? gcdA : 0
    let answerB = arrayA.allSatisfy { gcdB != 1 && $0 % gcdB != 0 } ? gcdB : 0
        
    return max(answerA, answerB)
}

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

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