Codility - CountDiv

아래 문제는 코딜리티에서 제공하는 CountDiv의 문제입니다🧑🏻‍💻

 

문제 제시

Write a function:
public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int
that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:
{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.
Write an efficient algorithm for the following assumptions:
A and B are integers within the range [0..2,000,000,000];
K is an integer within the range [1..2,000,000,000];A ≤ B.

문제 해결

import Foundation
import Glibc

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let startCount = A % K == 0 ? 1 : 0
    return (B / K + startCount) - (A / K)
}

 

사용된 개념

 - 삼항연산자

 - 시간복잡도

 - 차집합 개념

 

문제 뒷담화

해당 문제는 되게 간단했으나 루프를 돌거나 고차함수를 사용하여 풀려고 하면 시간 복잡도 때문에 애를 먹는 문제이다.

처음 아래와 같이 필터와 카운트를 이용하여 최소한의 조건을 돌려했지만 그렇게 된다면 시간 복잡도가 O(B-A)가 된다.

import Foundation
import Glibc

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let aToBNumbers = Array<Int>(A...B)
    return aToBNumbers.filter({ $0 % K ==0 }).count
}

이럴 경우 최대 20억의 수를 받아올때 시간 복잡도가 아주 어마어마해져 효율적으로 해당 알고리즘을 통과할 수 없다.

이에 B까지 K의 배수의 갯수를 구하고 A까지 K의 배수를 구하는것은 간단하니 둘을 구해준다.

그리고 A 즉 시작점이 K의 배수일 수 있으니 판별해주는 startCount를 산출해 더해준다.

이렇게되면 제일 효율적인 O(1)의 시간 복잡도를 가질 수 있다.

항상 코딜리티의 문제는 간단하나 시간 복잡도를 생각하여 기계처럼 풀 수 있는 능력을 요구하는것 같다.

화려한 코딩 스킬보다 한번 더 효율적인 생각을 하는 학습이 된다.

 

[참고자료]

https://app.codility.com/c/run/trainingXUFQ48-EMT/

Codility