Codility Lesson 12 - ChocolatesByNumbers( JAVA )

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

ChocolatesByNumbers coding task - Learn to Code - Codility

 

문제

- 양수 N, M이 주어지며, N은 원에 나열된 초콜렛들을 의미하며 0 ~ N-1까지 넘버링 되어있다.

- 0번째 초콜릿 부터 먹으며, 그 다음은 M번 째 초콜릿을 먹는다.

- 빈포장지를 만났을 때, 먹는 것을 멈춘다.

- 예시 : N=10, M=4일 때, 0, 4, 8, 2, 6 번째의 초콜릿을 먹게된다.

- 먹은 초콜릿의 개수를 구하는 것이 목표이다.( 위와 같은 예시에서는 return 5 )

 

제한조건

• N and M are integers within the range [1..1,000,000,000].

N, M은 1 ~ 1,000,000,000 사이의 수이다.( Integer의 범위 안에 있다 )

 

풀이

- gcd(최대공약수)를 구하는 것과 관련된 문제로 M과 N의 gcd를 구하는 문제로 해석된다.

- 예제에서 N=10, M=4일 경우 gcd = 2 -> N / 2 = 5, 답은 5가 된다.

- N=10, M=3일 경우 gcd=1로 모든 초콜릿을 다 먹을 수 있게 된다.

 

예상시간 복잡도 : 가늠 안됨...

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N, int M) {
        // write your code in Java SE 8
        int gcd = gcd(N, M);
        // System.out.println("gcd : " + gcd);
        int answer = N / gcd;
        return answer;
    }

    private int gcd(int n, int m){
        if( n % m == 0){
            return m;
        }else{
            return gcd(m, n % m);
        }
    }
}

 

 

손쉽게 해결!( gcd부분을 몰랐으면 해맸을 듯.. )