[LeetCode/Easy] 1175. Prime Arrangements

1. Input

1) int n

 

2. Output

1) 1부터 n까지의 수를 크기가 n인 배열에 담을 때, 다음을 만족하는 경우의 수를 1000000007로 나눈 나머지를 반환

- 배열의 인덱스는 [1, n]이다.

- 소수는 인덱스 값이 소수인 곳에만 위치할 수 있다.

 

3. Constraint

1) 1 <= n <= 100

 

4. Example

Input: n = 5 -> Output: 12

설명: 여러 경우 중 [1,2,5,4,3]는 유효한 순열이다. 그러나 [5,2,3,4,1]은 유효하지 않다. 1번째 인덱스의 값이 5인데, 1은 소수가 아니기 때문이다.

 

5. Code

1) 첫 코드(2023/06/08)

class Solution {
    public int numPrimeArrangements(int n) {
        int prime = 0;
        for(int i=2 ; i<=n ; i++){
            if(isPrime(i))
                prime++;
        }
        return (int)((fac(prime)*fac(n-prime))%1000000007);
    }

    static boolean isPrime(int i){
        boolean ans = i>1;
        for(int n=2 ; n<=(int)Math.sqrt(i) && ans; n++)
            if(i%n==0)
                ans = false;
        return ans;
    }

    static long fac(int n){
        long ans = 1;
        for(int i=2 ; i<=n ; i++)
            ans = (ans*i)%1000000007;
        return ans;
    }
}

- 100%, 30%