[ Codility 코딜리티 ] Lesson 5 CountDiv Python 파이썬 풀이

 

// 문제 요약

 

A, B, K 세 정수가 주어지면

A 이상 B 이하의 정수 중

K의 배수는 몇개인지 구해라.

 

// 문제 풀이

 

이 문제는 일종의 기믹을 쓴다.

수학적인 특징을 이용하는 것인데

어떤 구간을 K마다 자르면

완전한 subarray에는 반드시

1개의 K의 배수가 존재한다는

특성을 이용한다.

 

즉

주어진 구간의 길이를 K로 나눠서

마지막에 남는 나머지가 있다면

그 나머지 안에 K의 배수가 있는지만 검사해서

리턴하면 되는 방식이다.

 

 

코드부터 보자.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B, K):
    # write your code in Python 3.6
    len_AB = B + 1 - A

    if len_AB < K:
        for n in range(A, B + 1):
            if n % K == 0:
                return 1

    div, mod = divmod(len_AB, K)
    # last chunk
    for n in range(A + div * K, B + 1):
        if n % K == 0:
            return div + 1
    return div

 

우선은 A와 B 사이에 K의 배수가

단 하나도 없을 경우가 있기 때문에

B + 1 - A가 K보다 작은 경우를

따로 계산해준다.

 

그 다음은 B와 A사이의 거리를

K로 나누어서

나머지가 있는 경우

나머지에서 K의 배수를 찾아주고

아니면 그냥 몫을 리턴한다.

 

if문을 이용해서 나머지가 있는 경우와

없는 경우를 나눠서 생각해줄 수 있겠지만

성능에 크게 영향을 주지 않을 것으로 생각하여

이 풀이에는 적지 않았다.

 

해주면 더 좋을 것이다.