2601. Prime Subtraction Operation

문제

You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].
Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

• 배열이 하나 주어질때, 한 숫자에 한번씩 소수를 뺄수 있다.
• 배열이 오름차순으로 정렬되게 할수 있는가?

예시

[4,9,6,10]

• 4 - 3 = 1
• 9 - 7 = 2
• 6 - 0 = 6
• 10 - 0 = 10
• [1, 2, 6, 10] 인 오름차순 배열로 만들수 있다.

제한

• $1 <= nums.length <= 1000$
• $1 <= nums[i] <= 1000$
• $nums.length == n$

풀이법

• 먼저 범위 내인 1~1000 까지의 소수를 모두 구한다.
• nums에 대해 계산을 하는데, 맨 첫자리일 경우 0이 되지 않는 선에서 가장 뺄수 있는 큰 소수
  • 인덱스가 0 초과 하는 경우는
  • index i에 대해
    • nums[i] - nums[i-1], 즉 앞자리 수와의 차이 - 1 와 같거나 가장 가까우면서 작은 소수를 뺀다.
• 진행해 나가면서 오름차순이 아니라면 바로 False를 리턴한다.

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        primes = {2, 3, 5, 7, 521, 11, 523, 13, 17, 19, 23, 29, 541, 31, 547, 37, 41, 43, 557, 47, 563, 53, 569, 59, 571, 61, 577, 67, 71, 73, 587, 79, 593, 83, 599, 89, 601, 607, 97, 101, 613, 103, 617, 107, 619, 109, 113, 631, 127, 641, 131, 643, 647, 137, 139, 653, 659, 149, 661, 151, 157, 673, 163, 677, 167, 683, 173, 179, 691, 181, 701, 191, 193, 197, 709, 199, 719, 211, 727, 733, 223, 227, 739, 229, 743, 233, 239, 751, 241, 757, 761, 251, 257, 769, 773, 263, 269, 271, 787, 277, 281, 283, 797, 293, 809, 811, 307, 821, 311, 823, 313, 827, 317, 829, 839, 331, 337, 853, 857, 347, 859, 349, 863, 353, 359, 877, 367, 881, 883, 373, 887, 379, 383, 389, 907, 397, 911, 401, 919, 409, 929, 419, 421, 937, 941, 431, 433, 947, 439, 953, 443, 449, 967, 457, 971, 461, 463, 977, 467, 983, 479, 991, 997, 487, 491, 499, 503, 509}



        for i in range(len(nums)):
            diff = nums[i] - 1 if i == 0 else nums[i] - nums[i-1] - 1

            for j in range(diff, 1, -1):
                if j in primes:
                    nums[i] -= j
                    break

            if i != 0:
                if nums[i] <= nums[i-1]:
                    return False

        return True