Codility Lesson 11 - CountSemiprimes(JAVA)

https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_semiprimes/

CountSemiprimes coding task - Learn to Code - Codility

 

문제

- prime은 소수를 의미 : 2, 3, 5, 7, 11 ...( 1과 나 자신만이 약수인 수 )

- semiprime은 자연수 중 2개의 소수로 이루어진 수를 의미 : 4, 6, 9, 10, 14 ...

- M개의 정수들로 이루어진 P, Q배열이 주어질 때, Query K는 1 <= P[K] <= Q[K] <= N의 범위에서 semiprime의 개수를 의미한다.

- 예시 : N = 26, P[0] = 1 Q[0] = 26 P[1] = 4 Q[1] = 10 P[2] = 16 Q[2] = 20

- return [ 10, 4, 0 ]

 

제한조건

• N is an integer within the range [1..50,000];
• M is an integer within the range [1..30,000];
• each element of arrays P and Q is an integer within the range [1..N];
• P[i] ≤ Q[i].

N은 1 ~ 50000사이의 정수이다.

M은 1 ~ 30000사이의 정수이다.

P, Q배열의 각 원소들은 1 ~ N사이의 정수이다.

P[i] <= Q[i]

 

풀이

- PDF 문서 참조 Sieve of Eratosthenes와 Factorization 둘다 활용

- Sieve of Eratosthenes를 통해서 N까지에서의 소수들을 구할 수 있고, Factorization을 활용하여 소수가 아닌 수들의 해당하는 divdor를 구할 수 있음

- factorization으로 구해진 수들 중 해당하는 factor로 나눈 수가 prime인지 아닌지만 판별하여 수를 확인한다.

 

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

 

소스코드

// 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[] P, int[] Q) {
        // write your code in Java SE 8

        // prime은 소수를 뜻한다
        // semiprime이란 소수 2개의 곱으로 이루어진 것들을 의미한다
        // factorization을 활용하여 문제 풀이
        // P의 최소값과 Q의 최대값을 찾는다

        boolean[] primeArr = new boolean[N+1];
        // true로 초기화
        Arrays.fill(primeArr, true);
        primeArr[0] = primeArr[1] = false;

        int[] arrayF = new int[N+1];
        // 소수는 2부터 시작한다
        for( int i=2; i*i<N; i++ ){
            
            // prime number 찾기
            if( primeArr[i] ){
                int m = i*i;
                while( m <= N ){
                    primeArr[m] = false;
                    m += i;
                }
            }

            // factorization 찾기
            if( arrayF[i] == 0 ){
                int k = i*i;
                while( k <= N ){
                    if( arrayF[k] == 0 ){
                        arrayF[k] = i;
                    }
                    k += i;
                }
            }
        }

        int[] semiPrmieArr = new int[P.length];

        for( int i=0; i<semiPrmieArr.length; i++ ){
            int startIdx = P[i];
            int endIdx = Q[i];
            int semiCnt = 0;

            for( int j=startIdx; j<endIdx+1; j++ ){
                if( arrayF[j] != 0 ){
                    int mok = j / arrayF[j];
                    if( primeArr[mok] ) semiCnt++;  // primeArr에서 true일 경우 prime 값임
                }
            }

            semiPrmieArr[i] = semiCnt;
        }

        return semiPrmieArr;

    }
}

 

결과

time out과 wrong answer 이슈 발생

1트 실패...

 

2트 바로 도전

보완점

- factorization에서 N까지의 바로 semiprimes들을 구할 수 있을 것

- semiprimes을 구하면서 동시에 누적 횟수를 구해서 semiprime을 따로 카운트하지 않고 기록된 것에서 찾도록 수정

- startCnt 변수는 확인해 보면 예제문제에서 4~10, 5~10 구할 때 카운트 횟수가 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[] P, int[] Q) {
        // write your code in Java SE 8
        
        // 1. prime factor를 구하는 배열과 factorization을 구하는 배열을 각각 선언
        boolean[] primeArr = new boolean[N+1];
        int[] arrayF = new int[N+1];

        Arrays.fill(primeArr, true);    // false인 것은 prime(소수) 가 아닌 것들
        // 0과 1은 포함되지 않으므로 false로 초기화
        primeArr[0] = primeArr[1] = false;

        // 2. N까지의 prime factor와 factorization을 구하라
        for( int i=2; i*i<=N; i++ ){
            // prime 구하기
            if( primeArr[i] ){
                int k = i*i;
                while( k <= N ){
                    primeArr[k] = false;
                    k += i;
                }
            }

            // factorization 구하기
            if( arrayF[i] == 0 ){
                int m = i*i;
                while( m <= N ){
                    if( arrayF[m] == 0 ){
                        arrayF[m] = i;
                    }
                    m += i;
                }
            }
        }

        int[] semiprimes = new int[N+1];
        // 3. semiprimes를 N까지 구하기( 각 숫자에는 semiprime의 누적수를 가지고 있는다.)
        int semiCnt = 0;
        for( int i=4; i<N+1; i++ ){
            if( arrayF[i] != 0 ){
                int mok = i / arrayF[i];
                if( primeArr[mok] ){
                    semiCnt++;
                }
            }
            semiprimes[i] = semiCnt;
        }
/*
        for( int i=0; i<N+1; i++ ){
            System.out.println("semiprimes[" + i + "] : " + semiprimes[i]);
        }
*/
        int[] answer = new int[P.length];

        for( int i=0; i<P.length; i++ ){
            int startIdx = P[i];
            int endIdx = Q[i];

            int startCnt = startIdx==0?0:semiprimes[startIdx-1];
            int totalCnt = semiprimes[endIdx] - startCnt;
            
            answer[i] = totalCnt;
        }
        return answer;
    }
}

 

결과

 

구글링하지 않고 3일간 도전하고 PDF문서 이해하려고 하고 결국 성공했다ㅠ

 

사용한 JAVA메소드

Arrays.fill( 배열, 채울 요소 ) : 배열을 일괄 초기화 할 때 활용

https://crazykim2.tistory.com/545

[JAVA] Arrays.fill() 사용 방법(배열의 값 일괄초기화)

 

primeArr[0] = primeArr[1] = false 와 같이 동시 초기화도 가능하다.

 

다른 분들은 어떻게 했는지 참고하기 위해 구글링..

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

Codility Lesson11 - CountSemiprimes