30일 (2614. Prime In Diagonal) 소수구하기

You are given a 0-indexed two-dimensional integer array nums.

Return the largest prime number that lies on at least one of the diagonals of nums. In case, no prime is present on any of the diagonals, return 0.

Note that:

• An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself.
• An integer val is on one of the diagonals of nums if there exists an integer i for which nums[i][i] = val or an i for which nums[i][nums.length - i - 1] = val.

In the above diagram, one diagonal is [1,5,9] and another diagonal is [3,5,7].

 

Example 1:

Input: nums = [[1,2,3],[5,6,7],[9,10,11]]
Output: 11
Explanation: The numbers 1, 3, 6, 9, and 11 are the only numbers present on at least one of the diagonals. Since 11 is the largest prime, we return 11.

Example 2:

Input: nums = [[1,2,3],[5,17,7],[9,11,10]]
Output: 17
Explanation: The numbers 1, 3, 9, 10, and 17 are all present on at least one of the diagonals. 17 is the largest prime, so we return 17.

 

Constraints:

• 1 <= nums.length <= 300
• nums.length == numsi.length
• 1 <= nums[i][j] <= 4*10^6

 

 

    class Solution {
        public int diagonalPrime(int[][] nums) {

            Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
            int length = nums.length;
            int temp = length-1;

            for(int i = 0; i < length; i++) { // 1
                queue.add(nums[i][i]);
                queue.add(nums[i][temp--]);
            }

            if(queue.peek() == 1) return 0; // 2
            if(queue.peek() == 2) return 2;

            while(!queue.isEmpty()) {  // 3
                int largest = queue.poll();
                int sqrt = (int) Math.sqrt(largest)+1;

                for(int i = 2; i <= sqrt; i++) {
                    if(largest % i == 0) {
                        break;
                    }
                    if(i == sqrt) {
                        return largest;
                    }
                }
            }

            return 0;
        }
    }

 

0. 2차원배열 nums의 대각선을 구성하는 정수를 먼저 구한다, 그리고 그 대각선을 구성하는 정수 중 가장 큰 소수를 리턴한다.

한번 꼬아놨지만 문제가 원하는 바는 소수를 판별하고 소수 중 최댓값을 리턴하는 것이다.

 

1.  for문 한번으로 2차원 배열의 양 대각선을 구성하는 정수들을 내림차순 우선순위 큐에 담는다.

 

2. 1 <= nums[i][j] <= 4*10^6 조건에 따라 1이나 2의 리턴 값을 따로 생각한다.

 

3. 내림차순 우선순위 큐이므로 poll()은 nums의 대각선을 구성하는 가장 큰 정수가 나온다.

가장 큰 정수(largest)가 소수인지 아닌지 판별하고 소수가 맞다면 현재 가장 큰 정수이므로 가장 큰 소수가 되기때문에

largest를 리턴하면 된다.

 

평범한 결과가 나왔다.

 

소수 판별 ( 문제에서는 2번을 썼다.)

1. int i = 13일때, (13 / 2 ~ 12 )까지 나눴을때 나머지가 존재한다면 소수이다. (모두 대입)

2. int i = 13일때, (13/ 2 ~ 13의 제곱근 +1 )까지 나눴을때 나머지가 존재한다면 소수이다. (향상된)

3. 에라토스테네스의 채

 

 

 

 

https://leetcode.com/problems/prime-in-diagonal/submissions/1079770594/

LeetCode - The World's Leading Online Programming Learning Platform