[코딜리티] CountNonDivisible

 

▼ 문제 링크

CountNonDivisible coding task - Learn to Code - Codility

 

역시나 정답은 맞췄지만, 시간 복잡도에서 실패한 케이스

기존 배열의 값을 새로운 배열의 index로 전환하고 해당 index의 값을 기존 배열의 값의 총 개수로 변환하는 게 풀이의 핵심이었다. 이게 무슨 말이나면

original[i] = k 이고 original배열에서 값 k가 배열 original 내에 전부 n개 있을 때
이 배열을 new배열에 위에서 언급한 방법대로 바꾸면
new[k] = n 이 된다.

 

 

# 풀이 1
약수를 모두 구하고 배열의 요소를 비교하는 방법

import Foundation

public func solution(_ A : inout [Int]) -> [Int] {
    var result: [Int] = Array(repeating: 0, count: A.count)
    var divisors: Set<Int> = []

    for (index1, value1) in A.enumerated() {
        divisors = findDivisors(value1)

        for value2 in A {
            if !divisors.contains(value2) {
                result[index1] += 1
            }
        }
    }

    return result
}

private func findDivisors(_ num: Int) -> Set<Int> {
    var divisors: Set<Int> = []

    for i in 1..<num {
        if i * i > num {
            break
        }

        if num % i == 0 {
            divisors.insert(i)
            divisors.insert(num / i)
        }
    }
    divisors.insert(num)

    return divisors
}

내가 처음 시도했던 가장 기본적인 방법

findDivisors로 주어진 수의 약수를 모두 구하고, 배열 요소 하나하나 확인하면서 그 값이 약수 배열에 존재하는지 아닌지를 체크하는 방법

정답은 맞았지만 시간 초과가 나왔음

 

 

# 풀이 2
중복 요소의 개수를 구해 루프를 줄임

import Foundation

public func solution(_ A : inout [Int]) -> [Int] {
    var elements: Dictionary<Int, Int> = [:]
    var result: [Int] = Array(repeating: 0, count: A.count)
    var divisors: Set<Int> = []

    for value in A {
        if elements[value] == nil {
            elements[value] = 0
        }

        elements[value] = elements[value]! + 1
    }

    for (index, value) in A.enumerated() {
        divisors = findDivisors(value)

        for (element, count) in elements {
            if !divisors.contains(element) {
                result[index] += count
            }
        }
    }
    
    return result
}
private func findDivisors(_ num: Int) -> Set<Int> {
    var divisors: Set<Int> = []
    
    for i in 1..<num {
        if i * i > num {
            break
        }
        if num % i == 0 {
            divisors.insert(i)
            divisors.insert(num / i)
        }
    }
    divisors.insert(num)
    return divisors
}

풀이1과 비슷하지만, original[i] = k를 new[k] = n 로 바꾸는 로직을 추가했다.

모든 배열을 루프 돌면서 확인하지 않고 중복이 제거된, 요소의 개수를 의미하는 새로운 배열인 elements를 돌면서 non-divisor의 개수를 찾음

하지만 여전히 시간 초과

 

 

# 풀이 3
요소의 개수를 담은 새로운 배열 활용하기

import Foundation

public func solution(_ A : inout [Int]) -> [Int] {
    let aCount = A.count

    // 배열 A의 요소가 가질 수 있는 범위는 1~2*A.count (조건에 명시)
    // 1을 더해주는 건 배열의 0번째를 사용하지 않기 위함
    var elements = Array(repeating: 0, count: (aCount * 2) + 1)

    // 배열 A의 각 요소값에 해당하는 elements배열에 요소의 개수 만큼 +1
    // Ex. A[0] = 3 이면 elements[3] = 1
    for i in 0..<aCount {
        elements[A[i]] += 1
    }

    // non-divisor 요소의 개수
    var nonDivisors = Array(repeating: 0, count: aCount)

    for i in 0..<aCount {
        var divisors = 0
        var j = 1

        // A[i]의 약수 구하기
        while j * j <= A[i] {
            if A[i] % j == 0 {
                // A[i]의 약수에 해당하는 A의 요소의 개수를 합산
                divisors += elements[j]

                // A[i]가 j의 제곱일 경우 제외
                if A[i] / j != j {
                    divisors += elements[A[i]/j]
                }
            }
            
            j += 1
        }
        
        // 약수가 아닌 요소의 개수의 합이니까 총 개수에서 약수의 개수를 빼줌
        nonDivisors[i] = aCount - divisors
    }

    return nonDivisors
}

요소의 값을 나타내는 배열 A 대신, 배열 A에 담긴 요소의 개수를 표현하는 elements 배열을 새로 생성. divisors에 약수인 요소의 개수를 더해주고 마지막에 배열 A의 총 개수에서 뺀다.

이번엔 되겠지...! 했는데 배열의 크기가 매우 클 때 시간 복잡도가 O(n2) 가 나왔다.

어디선가 더 루프를 줄일 수 있는 방법이 있을 듯

 

 

# 풀이 4
진짜_정말_최종_마지막_파이널.swift

import Foundation

public func solution(_ A : inout [Int]) -> [Int] {
    let aCount = A.count

    // 배열 A의 요소가 가질 수 있는 범위는 1~2*A.count (조건에 명시)
    // 1을 더해주는 건 배열의 0번째를 사용하지 않기 위해
    var elements = Array(repeating: 0, count: (aCount * 2) + 1)

    // 배열 A의 각 요소값에 해당하는 elements배열에 요소의 개수 만큼 +1
    // Ex) A[0] = 3 이고 배열 A에 3이 하나 뿐이면 elements[3] = 1
    for i in 0..<aCount {
        elements[A[i]] += 1
    }
    
    // 중복 요소 확인용
    var duplicated = Array(repeating: -1, count: (aCount * 2) + 1)
    // non-divisor 요소의 개수
    var nonDivisors = Array(repeating: 0, count: aCount)
    
    for i in 0..<aCount {
        let aValue = A[i]
        
        // 이전에 이미 똑같은 요소가 나온 경우
        if duplicated[aValue] != -1 {
            nonDivisors[i] = duplicated[aValue]
            
        // 중복 요소가 아닌 경우
        } else {
            var divisors = 0
            var j = 1

            // A[i]의 약수 구하기
            while j * j <= A[i] {
                if A[i] % j == 0 {
                    // A[i]의 약수에 해당하는 A의 요소의 개수를 합산
                    divisors += elements[j]

                    // A[i]가 j의 제곱일 경우 제외
                    if A[i] / j != j {
                        divisors += elements[A[i]/j]
                    }
                }
                
                j += 1
            }
            
            // 약수가 아닌 요소의 개수의 합이니까 총 개수에서 약수의 개수를 빼줌
            nonDivisors[i] = aCount - divisors
            // 다음에 같은 요소가 또 나와 중복임을 확인하기 위해
            duplicated[aValue] = nonDivisors[i]
        }
    }

    return nonDivisors
}

이미 한 번 체크했던 요소를 다시 한 번 체크하는 것은 시간 낭비이므로 duplicated라는 배열을 추가함

duplicated 배열의 모든 요소의 초기값은 -1

약수 체크 루프를 한 번 돌고 나면 duplicated[aValue] = nonDivisors[i]가 되기 때문에 다음부터는 굳이 체크할 필요 없이 해당 값을 바로 nonDivisors 배열에 입력하면 된다.

풀이4를 통해 겨우 시간 복잡도 O(n log n)로 통과!