[Leetcode 2601번 문제] 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.

 

1차원 배열이 있다.

다음의 작업을 할 수 있는데. i인덱스 요소를 잡고, i보다 작은 소수 p를 고른다. 그리고 nums[i]에서 p를 뺀다

nums배열에 대해서 다음 작업을 할때 결과물이 increasing하게, 증가하는 함수를 만들 수 있나?

있다면 true를 아니면 false를 리턴

입력

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

출력

위의 작업이 가능한지 아닌지에 대한 bool값

과정

방향성이 존재하는 문제 같다. 왼쪽으로 갈수록 작아질 수록 좋다가 가능하고 오른쪽으로 갈 수록 클 수록 좋다가 가능하다.

그렇다면 맨끝은 반드시 2를 빼도 아무 문제가 없다. 끝값을 고정이 되어있는 것, 다행히 소수는 1000보다 작은수만 구하면 된다. 그렇기 때문에

1. 맨끝은 2를 빼는 것으로 고정
2. 그럼 다음수는 그 자체의 수 n[i]와 끝수에서 n[i + 1] 2를 뺀 수보다 커야한다.
3. 이걸 오른쪽 끝에서부터 왼쪽끝까지 반복하다 불가능하면 false가능하다면 true를 리턴

알고리즘

class Solution {
    map<int, int> greatest;
public:
    bool primeSubOperation(vector<int>& nums) {
        greatest[0] = 1;
        vector<int> primes (1001, 0);
        for (int i = 2; i < 1001; i++)
        {
            if (primes[i])
                continue;
            int stackI = i + i;
            greatest[i] = 1;
            while (stackI < 1001)
            {
                primes[stackI] = 1;
                stackI += i;
            }
        }
        int lastIndex = nums.size() - 1;
        int diff = -1;
        while (lastIndex >= 0)
        {
            auto maybe = greatest.upper_bound(diff);
            if (maybe == greatest.end() || maybe -> first >= nums[lastIndex])
                return false;
            nums[lastIndex] -= maybe -> first;
            if (lastIndex)
            {
                diff = nums[lastIndex - 1] - nums[lastIndex];
            }
            lastIndex--;
        }
        return true;
    }
};