[LeetCode] 2601. Prime Subtraction Operation

https://leetcode.com/problems/prime-subtraction-operation/description/?envType=daily-question&envId=2024-11-11

leetcode - Prime Subtraction Operation

문제 유형: 정수론, 수학, 그리디

문제 난이도: Medium

 

문제

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.

 

0-indexed의 정수 배열 nums가 주어진다.

다음의 연산을 마음껏 할 수 있다:

- 고르지 않은 인덱스 i를 골라서, nums[i]의 수에 nums[i]보다 엄격히 작은 소수 p를 골라서 p를 뺄 수 있다.

 

연산을 이용하여 엄격한 오름차순을 만들수 있으면 true, 아니면 false를 반환하시오.

 

풀이

각 인덱스를 순차적으로 연산을 적용하면서, 최대한 연산을 적용가능한선에서 최대한 큰 소수 p를 골라 빼서 적용시켜야 한다.

소수들을 배열에 오름차순으로 담는다.

 

이진탐색을 이용하여 가능한 가장 큰 소수 p를 찾는다.

만약 i = 0이고, p를 뺄 수 있다면, nums[0]에 p를 빼준다.

i > 0이라면, 앞의 수보다 큰 최소의 nums[i] - p를 구하기 위해 조정한다.

 그 뒤, 유효한 p가 없고 현재 수가 이전의 연산된수보다 작거나 같다면, 불가능하므로 false를 반환한다.

 그게 아니라면, p만큼 뺀 채로 저장하거나 p가 없다면 그대로 요소를 유지한다.

 

배열을 순회하면서 연산을 한 번씩 적용을 시도하는데 무사히 끝냈다면, 유효하므로 true를 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool isPrime(int x) {
        int r = sqrt(x)+1;
        for(int i = 2; i <= r; ++i) {
            if(x % i == 0) return false;
        }
        return true;
    }
    bool primeSubOperation(vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> primes;
        primes.push_back(2);
        for(int i = 3; i < maxNum; ++i) {
            if(isPrime(i)) primes.push_back(i);
        }

        int n = nums.size();
        int m = primes.size();
        for(int i = 0; i < n; ++i) {
            int idx = lower_bound(primes.begin(), primes.end(), nums[i]) - primes.begin();
            while(idx >= m || (idx > 0 && primes[idx] >= nums[i])) idx--;
            if(i == 0) {
                if(nums[i] - primes[idx] > 0) nums[i] -= primes[idx];
            } else {
                while(idx >= 0 && nums[i] - primes[idx] <= nums[i-1]) idx--;
                if(idx == -1 && nums[i] <= nums[i-1]) return false;

                if(idx != -1) nums[i] -= primes[idx];
            }
        }
        return true;
    }
};