[Swift 알고리즘] Codility - CountDiv

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - CountDiv" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

CountDiv coding task - Learn to Code - Codility

 

풀이

이번 문제는 A <= i <= B 에서 K로 나누어 떨어지는 i의 개수를 구하는 문제입니다.

A, B는 0 ~ 20억의 수로 O(N)으로도 풀 수 없는 문제죠. (O(logN)도 안 될듯)

이렇게 대놓고 커버리니 O(N) 풀이는 아예 제외할 수 있어서 오히려 좋습니다.

 

그럼 O(1)로 풀 수 있는 방법이 무엇인지 생각해 봅시다.

B를 K로 나눈 값은 0 ~ B까지의 i의 배수 개수입니다.

A를 K로 나눈 값은 0 ~ A까지의 i의 배수 개수입니다.

즉, B / K - (A-1) / K는 A ~ B의 i의 배수 개수를 구할 수 있는 것이죠

 

이때, Int로 나눗셈 연산을 하면 반올림이 되어 저는 floor로 처리해주었습니다.

큰 범위에 살짝 당황했지만 너무 커서 오히려 좋았던 문제네요.

 

감사합니다!

 

전체 코드

import Foundation

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    // write your code in Swift 4.2.1 (Linux)

    let minCount: Int = Int(floor(Double(A-1) / Double(K)))
    let maxCount: Int = Int(floor(Double(B) / Double(K)))

    // print("minCount: \(minCount) / maxCount: \(maxCount)")

    return maxCount - minCount
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.