Codility Lesson12. Euclidean algorithm - ChocolatesByNumbers

Tasks

https://app.codility.com/programmers/lessons/12-euclidean_algorithm/

내 풀이

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N, M) {

    let ans = [];
    let X=0;

    for (i=0; i<N; i=((X+M)%N)) {

        if (i === ans[0]) {
            break
        }

        ans.push(i)
        X = i

    }

    return ans.length ? ans.length : 0
}

66%

이보다 더 빠른 알고리즘이 존재

다른 풀이

function gcd(a, b) {
    // 회귀를 통해 최대 공약수를 구해줌
    if (a % b === 0) {
        return b;
    }
    return gcd(b, a % b);
}

function solution(N, M) {
    let ans = [];
    let X = 0;
    // 최대공약수를 활용하여
    let g = gcd(N, M);
    // N과 M을 나누어 시간 복잡도를 줄임
    let new_N = N / g;
    let new_M = M / g;

    for (let i = 0; i < new_N; i++) {
        ans.push(X);
        // 이렇게 되면 들어가는 값이 다 절반이 돼서 들어감
        // 어차피 값의 크기에 상관없이 반복만 보면 되므로 줄이고 실행
        X = (X + new_M) % new_N;
    }

    return ans.length;
}

하지만 이것조차도 N이 매우 큰 값일 땐 불가 75%

최종 코드

결국 최대공약수로 나눈 값을 활용하여 최소 공배수를 구한다음
최소 공배수와 M의 나눈 값이 곧, 다시 돌아오는 차례...

function gcd(a, b) {
    if (a % b === 0) {
        return b;
    }
    return gcd(b, a % b);
}

function solution(N, M) {
    let g = gcd(N, M);
    let new_N = N / g;
    let new_M = M / g;
    let lcm = new_N * new_M * g; // 최소공배수
    return lcm / M;
}