코딩 테스트 - ChocolatesByNumbers

두 개의 양의 정수 N과 M이 주어진다. 정수 N은 0에서 N-1까지 번호가 매겨진 원 안에 배열된 초콜릿의 수를 나타냅니다.

초콜릿을 먹기 시작합니다. 초콜릿을 먹고 나면 포장지만 남깁니다.

0번 초콜릿을 먹는 것으로 시작합니다. 그런 다음 원에 있는 다음 M-1 초콜릿 또는 포장지를 생략하고 다음 것을 먹습니다.

더 정확히 말하면, 초콜릿 숫자 X를 먹었다면 다음에 숫자 (X + M) 모듈로 N(나누기의 나머지)이 있는 초콜릿을 먹을 것입니다.

빈 포장지를 만나면 식사를 중단합니다.

예를 들어, 주어진 정수 N = 10 및 M = 4. 다음 초콜릿을 먹게 됩니다: 0, 4, 8, 2, 6.

목표는 위의 규칙에 따라 먹을 초콜릿의 수를 세는 것입니다.

함수 작성:

class Solution { public int solution(int N, int M); }

두 개의 양의 정수 N과 M이 주어지면 먹을 초콜릿의 수를 반환합니다.

예를 들어 주어진 정수 N = 10 및 M = 4. 위에서 설명한 대로 함수는 5를 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성 하십시오.

• N과 M은 [ 1 .. 1,000,000,000 ] 범위 내의 정수 입니다.

ㅇㅋ... (번역기로 해결 될 정도의 난이도)

0 4 8 2 6이 뭔지는 ↓ 요걸로 돌려보면 알 수 있음.

    public int solution(int N, int M) {

        int temp = 0;

        int answer = 0;

        while(true){

            temp = (temp+M)%N;        

            answer++;

            if(temp == 0){

                break;

            }        

        }

           

        return answer;

    }

일단 요렇게 짜면 timeOut 통과가 안된다!

그러니 이렇게 푼다!

package codility;

public class ChocolatesByNumbers_230108 {

    public static void main(String[] args) {

        ChocolatesByNumbers_230108 c = new ChocolatesByNumbers_230108();

        int N = 10;

        int M = 4;

        System.out.println(c.solution(N, M));

    }

   

    public int solution(int N, int M) {

        //유클리드 호제법을 이용해서 푼다.

        //N~M까지 최대 공약수를 구한 뒤에

        //N을 최대공약수로 나누면 초콜릿 개수가 반환된다

        return N / gcd(M, N);      

    }

     

     

      private int gcd(int n1, int n2) {

        if (n1 % n2 == 0) {

          return n2;

        } else {

          return gcd(n2, n1 % n2);

        }

      }

}