Codility: CountDiv (Python)

주제

Lesson 5: Prefix Sums

 

난이도

Medium

 

문제

Write a function:
def solution(A, B, K)
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.

 

세 숫자 A, B, K에 대해서 A~B 사이의 숫자 중 K로 나눠떨어지는 (즉, K의 배수인) 수의 개수를 카운트하는 문제이다.

A와 B는 0부터 매우 큰 숫자가 가능하며, K 또한 1부터 매우 큰 숫자까지 가능하다. 단, A <=B이다.

또한 efficient해야한다.

 

풀이

역시 efficient하게 풀라는 문제는 inefficient하게 푼 다음에 효율적으로 바꿔야 제맛이지만 이번에는 바로 효율적으로 풀 수 있었다. 그리고 이번에는 prefix sum 단원에 맞게 바로 풀 수 있었다. 

 

prefix sum은 부분합을 구할 때 요긴하게 쓸 수 있다. 그리고 이번 문제도 부분합은 없으나, 비슷한 풀이로 해결할 수 있다. 

 

 - A <= X <= B 이고, X % K == 0인 X의 갯수를 구해야한다.

 - 따라서 일단, B보다 작거나 같으면서 동시에 K로 나눠떨어지는 수의 개수를 구한다. 해당 개수는 B/K 값과 같다. (단, python에서는 나누면 float형으로 나오므로 int형으로 버림했다.) ... (1)

 - 그 후 A보다 작거나 같으면서 동시에 K로 나눠떨어지는 수의 개수를 구한다. 해당 개수는 A/K값과 같다. 단, 여기서 A가 K에 나눠떨어진다면 A도 포함되어야 하므로 A/K +1을 해줘야한다. ... (2)

 - 그러면 A보다 크거나 같으면서 B보다 작거나 같은, K로 나눠떨어지는 수의 갯수는 (1) - (2)와 같다. 

 

즉, B이하, A이상인 수 중에서 K로 나눠떨어지는 수를 구하는 것이므로, B까지 구한 후에, A이하의 수 중 K로 나눠떨어지는 수를 빼주면 간단하게 'A이상 B이하인 수이자 K로 나눠떨어지는 수'라는 조건을 만족하게 된다. 

 

코드

# 1~B까지 K로 나눠지는 수의 개수 (1)
# 1~A까지 K로 나눠지는 수의 개수 (2)
# (1) - (2)
# O(1)
def solution(A, B, K):
    divide_B = int(B / K)
    # 만약 A가 나누어 떨어진다면 해당 A도 포함되어야 하므로 A자체는 빼지 않도록 한다.
    if A % K == 0:
        divide_A = int(A / K) - 1
    else:
        divide_A = int(A / K)

    return divide_B - divide_A

 

시간복잡도

단순히 나눗셈 계산만 하고 있다.

따라서 O(1)이다. 

 

 

결과

codility 결과

 

솔직히 풀이방법을 10분내로 찾아서 너무 짜릿했는데(ㅋㅋㅋㅋㅋㅋㅋㅋㅋ) 아무래도 최근에 중2 학생들 수학 가르치면서 이런 저런 꼼수들(?)을 보다보니 자연스레 금방 떠오른 것이 아닐까 싶다. 이래서 수학 전공하는 사람들이 알고리즘을 잘 한다는 것 같다.