[Swift] CountNonDivisible 코딜리티 코딩테스트

주어진 배열 값중 약수가 아닌 갯수를 세어

배열값으로 리턴해주는 문제이다.

A[0] = 3
    A[1] = 1
    A[2] = 2
    A[3] = 3
    A[4] = 6
the function should return [2, 4, 3, 2, 0], as explained above.

3의 약수가 아닌 2,6 ← 두개이므로 2

1의 약수가 아닌 모든값

2의 약수가 아닌 3,3,6 ← 3개이므로 3

위 해답을 찾기위해 가장 단순한 방법은

반복문을 돌려 약수인지 아닌지 조건을 걸어 카운팅후 배열에 넣어

리턴하는 방법이다.

public func solution(_ A : inout [Int]) -> [Int] {
    if(A.count == 1){return [0]}
    var arr = [Int]()
    var dict = [Int:Int]()

    func countNonDivisor(index:Int,number:Int) -> Int{
        var divisorCount = 1
        for i in 0..<A.count{

            if(index != i) {
                if(number % A[i] == 0){
                    divisorCount += 1
                }
            }
            
        }
        return A.count - divisorCount
    }

    for i in 0..<A.count{
        if let valueFromDict = dict[A[i]] {
            arr.append(valueFromDict)    
        }else{
            let nonDivisorCount = countNonDivisor(index:i,number:A[i])
            arr.append(nonDivisorCount)
            dict[A[i]] = nonDivisorCount
        }
       
    }

    return arr
}

number % A[i] == 0 이부분이 약수를 구하는 조건이다.

다만 이미 구해진 갯수에 대해서는 countNonDivisor 함수를 타지않고

dict에서 꺼내 사용했다.

그러나 O(N**2) 가 적용되어 시간 초과를 했다.

해답은 이렇다.

제공받는 값의 범위는 1 ~ N(배열의길이)* 2 이다.

예시는 총 5의 배열길이 이므로 1~10 사이 값이 들어올것이다.

[3,1,2,3,6] 를 예시로 이런 배열을 만들어낸다.

[0,1,1,2,0,0,1,0,0,0,0]

배열의 총 길이는 10이고

값은 값의 갯수를 의미한다. 1은1개, 2는 1개, 3은2개 ,6은 1개이다.

이 배열의 값을 나중에 참조할것이다.

해당 배열을 Count 라고 하자.

// A = [3,1,2,3,6]
var count = Array(repeating: 0, count: (2 * A.count)+1)
var arr = [Int]()
for i in 0..<A.count{
    count[A[i]] += 1
}
//[0,1,1,2,0,0,1,0,0,0,0]

그리고 이제 약수가 아닌 갯수를 찾기위해 주어진 배열만큼 반복을 시킬것이다.

처음으로 A[0] = 3 이 들어온 경우

기존에 약수 찾기를 했던것 처럼 (이전글 참조)

j*j ≤ 3 까지만 반복문을 돌릴것이다. (j = 1 부터 시작)

j = 1 인경우

3 % j == 0 의 조건이 성립한다 ⇒ 1은 3의 약수이다.

추가로 3 / 1 (=3) 또한 3의 약수이다.

그렇다면 여기서 Count배열을 사용한다.

Count 배열에서 1의 갯수와 3의 갯수를 꺼내온다.

1의 갯수 = 1 / 3의 갯수 = 2

그러면 A 배열의 모든 수에서 3개를 뺀 2개가

A[0] = 3 일경우의 약수가 아닌 갯수가 된다.

public func solution(_ A : inout [Int]) -> [Int] {
    
    var count = Array(repeating: 0, count: (2 * A.count)+1)
    var arr = [Int]()
    for i in 0..<A.count{
        count[A[i]] += 1
    }
    for i in 0..<A.count{
        var divisors = 0
        var j = 1
        while j*j <= A[i] {
            if(A[i] % j == 0){
                if(A[i] == j*j){
                    divisors += count[j]
                }else{
                    divisors += count[j]
                    divisors += count[A[i]/j]
                }
            }
            j += 1
        }
        arr.append(A.count - divisors)
    }
    
    return arr
}