[Codility] CountSemiPrime 풀이 정리 (Java)

source 는 Github 에 있습니다.

문제

• 문제

풀이

첫번째 풀이

• 전체적인 concept 은 P 의 최소 값을 구한 후, P~N 까지 SemiPrime 을 구해서 cache 에 저장합니다.
  • cache[P+2] 라는 것은 P+2 까지 위치에서 SemiPrime 이 몇 개인지를 나타내는 것입니다.
  • 예를 들면, P가 4 이고 N 이 10이면, cache[4] = 1 이고, cache[10] = 4 입니다.
• P, Q 를 순회하면서 cache[Q[i]] - cache[P[i]] 를 구합니다.
  • 이 수식이 의미하는 바는 Q[i] 에서의 SemiPrime 의 개수에서 P[i] SemiPrime 수를 빼서 구하겠다는 것입니다.
  • 주의할 것은 cache[Q[i]] - cache[P[i]] 를 구할 때, P[i] 가 SemiPrime 이면 +1 을 해줘야하는 것입니다.
• SemiPrime, Prime 을 구할 때, root 를 적용한 값까지만 구해도 됩니다.
• 시간복잡도 O(nlogn), 공간복잡도 O(n)

source

    public int[] solution(int N, int[] P, int[] Q) {
        int[] cache = new int[N + 1];
        int[] arrayP = new int[P.length];
        Arrays.fill(arrayP, Integer.MAX_VALUE);

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

        for (int i = 0 ; i < P.length ; i++) {
            arrayP[i] = P[i];
        }

        Arrays.sort(arrayP);


        int min = arrayP[0];
        cache[min] = isSemiPrime(min) ? 1 : 0;
        for (int i = min + 1 ; i <= N ; i++) {
            cache[i] = cache[i-1] + (isSemiPrime(i) ? 1 : 0);
        }

        // P, Q 를 순회
        for (int i = 0 ; i < P.length ; i++) {
            result[i] = cache[Q[i]] - cache[P[i]];
            result[i] += isSemiPrime(P[i]) ? 1 : 0;
        }
        return result;
    }

    /**
     * X 라는 양수가 있다고 가정
     * X = A * B 로 이루어짐.
     * 이 때, A 또는 B 중 1개는 루트 X 보다 크거나 작아야 함.
     * ex) X = 36 이라 한다면, 1*36, 2 * 18, 3 * 12, ... , 18 * 2, 36 * 1 이런식으로 진행이 됨.
     *     위와 같이 2개의 숫자중 1개는 반드시 루트 X 보다 크거나 작아야 함.
     *     그렇다면 루트 X 보다 크거나 작은 숫자는 소수여야 prime 겠지?
     *
     * 시간복잡도 O(루트n)
     * @param num
     * @return
     */
    private boolean isPrime(int num) {
        if (num < 2) {
            return true;
        }

        for (int i = 2 ; i <= Math.sqrt(num) ; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private boolean isSemiPrime(int num) {
        boolean isExistSemiPrime = false;

        if (num < 2) {
            return false;
        }

        for (int i = 2 ; i <= Math.sqrt(num) ; i++) {
            if (num % i == 0) {
                if ( !isPrime(i) || !isPrime(num / i)) {
                    return false;
                } else if (isExistSemiPrime) {
                    return false;
                } else {
                    isExistSemiPrime = true;
                }
            }
        }
        return isExistSemiPrime;
    }