Codility Lesson 12 - CommonPrimeDivisors( JAVA )

 

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

CommonPrimeDivisors coding task - Learn to Code - Codility

 

문제

- prime divisor( 이하 pd )란 P라는 정수를 나눌 수 있는 소수를 의미한다.

- 예를들어, 20의 pd는 2, 5가 된다.

- 우리의 목표는 N, M 2개의 양수들에서 동시에 가진 pd를 구하는 것이다.

- 예시

• N = 15 and M = 75, the prime divisors are the same: {3, 5};
• N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};
• N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.

15와 75의 공통된 pd는 {3, 5}이다.( 15 -> {3, 5} / 75 -> {3, 5} )

10과 30의 공통된 pd는 {2, 5}이다.( 10 -> {2, 5} / 30 -> {2, 3, 5} )

9와 5의 공통된 pd는 없다.( 9 -> {3} / 5 -> {5} )

- 비어있지 않은 Z개의 정수들을 가진 배열 A, B가 주어질 때, 정확히 pd가 같은 원소의 인덱스(K)의 개수를 구하라.

 

- 예시 : A[0] = 15 B[0] = 75 A[1] = 10 B[1] = 30 A[2] = 3 B[2] = 5

- return 1, ( 15, 75 ) 만이 같은 pd set을 가지고 있다.

 

제한조건

• Z is an integer within the range [1..6,000];
• each element of arrays A and B is an integer within the range [1..2,147,483,647].

Z는 1 ~ 6000사이의 정수이다.

A, B 배열의 원소들은 1 ~ 2,147,483,647 사이의 정수이다.

 

풀이

- 같은 소인수(소수)를 가지고 있을 경우에만 해당하는 것을 착안하여 문제 풀이

- 두 수의 최대 공약수를 구한다.( PDF의 gcd를 나누기로 구하는 것 참조 )

- 최대공약수로 두 수를 나눈다.( 최대공약수가 1인 경우엔 노카운트 )

- 나누어진 두 수를 나누기 전의 각각의 다른 수를 나누어 나머지가 모두 0인 경우는 카운트, 아닌 경우는 노카운트

- 총 개수를 리턴한다.

 

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

 

소스코드( 1트, PDF로 gcd 구하기 )

// 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[] A, int[] B) {
        // write your code in Java SE 8
        int Z = A.length;

        int cnt = 0;
        for( int i=0; i<Z; i++ ){

            int N = A[i];
            int M = B[i];
            int max = N >= M?N:M;
            int min = N >= M?M:N;
            
            // System.out.println("max : " + max + " / min : " + min);
            int tmpGcd = gcd(max, min);
            // System.out.println("tmpGcd : " + tmpGcd);
            if( tmpGcd == 1 ) continue;

            int resMax = max / tmpGcd;
            int resMin = min / tmpGcd;

            if( min % resMax == 0 && max % resMin == 0 ){
                cnt++;
            }
        }

        return cnt;
    }

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

testcase
([65, 5, 24, 18427, 2147483646], [120, 5, 36, 12382438, 1073741823])

 

결과

 

timeout은 안났는데.. 예외케이스 처리를 못한듯 하다..

명일 다시풀이ㅠㅠ

 

2022/05/13( 2트, PDF로 gcd 구하기 )

수정사항

- tmpGcd( 최대공약수 ) == 1일 때, continue 했던 부분을 삭제( gcd가 1일 때 예외처리를 해버려서 [1], [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[] A, int[] B) {
        // write your code in Java SE 8
        int Z = A.length;

        int cnt = 0;
        for( int i=0; i<Z; i++ ){

            int N = A[i];
            int M = B[i];
            int max = N >= M?N:M;
            int min = N >= M?M:N;
            
            // System.out.println("max : " + max + " / min : " + min);
            int tmpGcd = gcd(max, min);
            // System.out.println("tmpGcd : " + tmpGcd);
            // if( tmpGcd == 1 ) continue;

            int resMax = max / tmpGcd;
            int resMin = min / tmpGcd;

            if( min % resMax == 0 && max % resMin == 0 ){
                cnt++;
            }
        }

        return cnt;
    }

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

 

결과

 

 

구글링 해오기..

참고한 블로그

https://sustainable-dev.tistory.com/39

Codility Lesson12 - CommonPrimeDivisors

https://mirae-kim.tistory.com/135

[Codility] Lesson12 - Euclidean algorithm: Common Prime Divisors

 

2022/05/13( 3트, 구글링 후 클론 코딩 )

 

소스코드

// 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[] A, int[] B) {
        // write your code in Java SE 8
        int Z = A.length;

        int cnt = 0;
        for( int i=0; i<Z; i++ ){

            int N = A[i];
            int M = B[i];
            int max = N >= M?N:M;
            int min = N >= M?M:N;
            
            int gcd = getGcd(max, min);

            int gcd_n = 0;
            int gcd_m = 0;

            while( gcd_n != 1){
                gcd_n = getGcd(N, gcd);
                N = N / gcd_n;
            }

            while( gcd_m != 1 ){
                gcd_m = getGcd(M, gcd);
                M /= gcd_m;
            }


            if( N == 1 && M == 1 ){
                cnt++;
            }
        }

        return cnt;
    }

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

 

- 이해한 바로는, 최대공약수란 즉 N, M 두 수의 공통인수를 가진 수 이다.

- gcd( N, M )과 각 N, M이 모두 공통의 인수를 가지고 있으면, 최대공약수를 계속 구해서 나눠주면 1이 나오게 될 것이다.

- 모두 공통의 인수를 가지지 않는다면 1이 나오지 않을 것

( 뭔가 말로 설명이 안된다... )