[LeetCode] 2601. Prime Subtraction Operation - Python

 

문제 설명

---

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.

 

문제 예제

---

Example 1:

Input: nums = [4,9,6,10]
Output: true
Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

Example 2:

Input: nums = [6,8,11,12]
Output: true
Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

Example 3:

Input: nums = [5,8,3]
Output: false
Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

 

제한 사항

---

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

 

내 풀이

import math

def make_prime_num(n):
    prime = [True for i in range(n+1)]
    prime[0] = False
    if n > 0:
        prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if prime[i]:
            j=2
            while i * j <= n:
                prime[i*j] = False
                j+=1

    return prime

def check_strictly_sort(nums):
    for i in range(1, len(nums)):
        if nums[i] <= nums[i-1]:
            return False
    return True

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True

        max_num = max(nums)
        prime = make_prime_num(max_num)
        for j in range(nums[0]-1, -1, -1):
            if prime[j]:
                nums[0] -= j
                break

        for i in range(1, len(nums)):
            if check_strictly_sort(nums):
                return True

            for j in range(nums[i]-1, -1, -1):
                if prime[j] and nums[i] - j > nums[i-1]:
                    nums[i] -= j
                    break

        return False

 

이 문제는 nums의 각 요소를 그 요소보다 작은 소수로 뺀 값을 저장했을 때, nums가 strictly increasing array가 될 수 있는 지 판별하면 되는 문제였다.

 

• ex) Input이 [6, 4, 5]라고 했을 때, 첫번째 요소인 6보다 작은 소수 중 5를 선택하여 6-5의 값인 1로 저장하면 [1, 4, 5]가 된다. 이 때 [1, 4, 5]는 strictly increasing array를 만족하기 때문에 True를 반환

 

따라서, 처음에 에라토스테네스의 체 알고리즘을 사용하여 nums에 있는 최대 요소보다 작은 소수 리스트를 확인할 수 있는 prime이라는 리스트를 생성했다.

 

 

이를 통해, 각 요소를 순차적으로 탐색하여 그 요소보다 작은 소수 중 최대한 큰 값을 빼면서 이전 요소보다는 크게 만들 수 있는 지 확인했다.

 

 

그리고 이게 가능하다면 nums의 요소를 업데이트하고 strictly increasing array를 만족하는 지 확인하여 만족하면 True를 반환, 아니면 다음 요소로 넘어가 앞선 과정을 반복하게 끔 구현하였다.

 

 

결국 모든 요소를 탐색했음에도 strictly increasing array를 만족하지 않으면 False를 반환한다.

 

 

에라토스테네스의 체를 응용하는 문제는 많이 접해보지 못했는데 이 문제를 통해 한번 더 리마인드하게 된 것 같아서 좋았다.

---

[LeetCode] 2601. Prime Subtraction Operation