[Easy] ChocolatesByNumbers

[문제]

원 형태로 놓인 N개의 초콜렛을 M칸씩 이동하며 먹었을 때 먹을 수 있는 초콜렛의 수를 세는 문제

 

[코드]

시간복잡도 : O(N+M) (성능 테스트 Fail)

def solution(N, M):
    # write your code in Python 3.6
    answer=1
    check = [0] * N
    check[0]=1
    current=0
    while True :
        current = current + M
        if check[current%N] == 1 :
            break;
        else :
            check[current%N] = 1
            answer = answer+1
    return answer

시간복잡도 : O(log(N+M)) (성능 테스트 Pass)

최대 공약수 활용

import math
def solution(N, M):
    # write your code in Python 3.6
    gcdvalue = math.gcd(N,M)

    if gcdvalue==0 :
        return N
    else :
        return int(N/gcdvalue)