[Codility] ChocolatesByNumbers

ChocolatesByNumbers

1차 시도

def solution(N, M):
    # write your code in Python 3.6
    eat = 1
    lo = M%N
    while lo!=0:
        lo = (lo+M)%N
        eat+=1
    return eat

답은 맞는데 performance에서 걸렸다.

2차 시도

euclidean algorithm을 사용하면 시간 복잡도가 크게 개선된다.

def solution(N, M):
    # write your code in Python 3.6
    if N==1:
        return 1
    n = euclid(N,M)
    return int(N/n)

def euclid(N, M):
    if M==0:
        return N
    else:
        return euclid(M, N%M)

O(log(N+M))의 복잡도