Codility Lesson12 - ChocolatesByNumbers

🔍 문제

---

 

N개의 초콜릿을 원 형태로 나열한 뒤, 0번째 초콜릿을 먹고 포장지만 남긴다. 그리고나서 현재 먹은 초콜릿 자리 + M의 자리에 있는 초콜릿을 먹는다. 원의 형태로 나열되어 있으므로 초콜릿의 자리는 (i + M)%N의 공식으로 구하면 된다. 이 순서로 초콜릿을 먹어가면서 이미 먹고 포장지만 남은 초콜릿의 자리로 다시 돌아오게된다면 먹는것을 멈춘다. 이 과정을 거쳤을 때 먹게되는 초콜릿의 개수를 구하면 된다.

 

ChocolatesByNumbers coding task - Learn to Code - Codility

 

✏️  풀이 - JavaScript

---

 

단순하게 풀어보았는데, N개의 요소를 가지는 배열을 만들어주고, 값을 true로 넣어준다. 그리고나서 초콜릿을 먹게되는 경우 값을 false로 바꿔주고, 이미 값이 false인 요소를 만나면 for문을 빠져나오도록 만들었다.
복잡도는 O(N + M)이 나왔는데도 performace test에서 25%가 나왔다. time limit에 비해 0.272sec인데 0.584sec이 나와서 통과하지 못했다.

function solution(N, M) {
    if(N === 1) return 1;

    let arr = [];
    for(let i = 0; i < N; i++) {
        arr.push(true);
    }

    let cnt = 0;

    for(let i = 0; i < N; i++) {
        let idx = (i * M) % N
        if(arr[idx] === true) {
            arr[idx] = false;
            cnt++;
        } else {
            break;
        }
    }

    return cnt;
}

다음은 유클리드 호제법을 이용해서 풀어보았다. 코드도 훨씬 짧아졌고 복잡도도 무려 O(log(N+M))으로 줄어들었다.

 

유클리드 호제법은 링크로 가면 자세히 볼 수 있다 👉 유클리드 호제법(Uclidean algorithm)

 

초콜릿을 먹는 index만 보면 0부터 시작해서 N과 M의 최대 공약수의 배수(< N)이다.
문제의 예시로 보면, N = 10이고 M = 4이면 결국에 먹게되는 초콜릿의 index는 0, 2, 4, 6, 8 이다.
따라서 N과 M의 최대 공약수 2를 구해준 후에 N(<=N)까지의 최대공약수의 배수 개수를 구해주었다. 먹게되는 초콜릿의 index에는 N이 포함되지 않지만 개수 구할때 어차피 0번째 초코렛은 무조건 먹고 시작하므로 따로 N 이전까지의 최대공약수의 배수 갯수 + 1을 해주지 않고 범위를 N을 포함해서 최대 공약수의 배수 개수를 구하였다.

 

Correctness와 Performance test 모두 100%로 통과하였다.

function solution(N, M) {
    if(N === 1) return 1; //N이 1인 경우

    const gcd = getGCD(M, N);

    return parseInt(N / gcd); //최대공약수 배수의 개수

    function getGCD(N, M){
        if(M === 0) return N;
        return getGCD(M, N % M);
    }
}