문제 링크

• 배열 길이, 최대값이 최대 1000까지라서 그냥 이렇게 해도 되는건가..
• 에라토스테네스의 체 최적화 구현.

내 코드

추가 TC

• {998, 2}: true
• {2, 2}: false
• {9, 13, 19, 7}: false

4 제출 만에 Solve

• sieve of eratosthenes, binary search
• 6ms, 32.64MB

class Solution {
public:
	bool primeSubOperation(vector<int>& nums) {
		const int MAX = 1000;
		vector<int> primes, visited(MAX, 0);

		for (int i{ 2 }; i < MAX; ++i) {
			if (!visited[i]) {
				for (int j{ i*i }; j < MAX; j += i) {
					visited[j] = 1;
				}
				primes.push_back(i);
			}
		}

		auto it = lower_bound(begin(primes), end(primes), nums[0] - 1);
		if (it != end(primes)) { // not found
			while (it != begin(primes)) {
				if (*it == nums[0]) --it;
				else {
					if (nums[0] - *it > 0) break;
					else --it;
				}
			}
			if (nums[0] > *it) nums[0] -= *it;
		}

		// 1, 9
		// 2 ~
		// 7
		for (int i{ 1 }, e = static_cast<int>(nums.size()); i < e; ++i) {
			it = lower_bound(begin(primes), end(primes), nums[i] - (nums[i - 1] + 1));
			if (it == end(primes)) {
				if (nums[i] <= nums[i - 1]) return false;
				continue;
			}
			
			// 가능한 가장 큰 원소 찾기
			while (it != begin(primes)) {
				if (*it == nums[i]) --it;
				else {
					if (nums[i] - *it > nums[i - 1]) break;
					else --it;
				}
			}

			if (nums[i] - *it > nums[i - 1]) {
				nums[i] -= *it;
			}
			else if (it == begin(primes)) {
				if (nums[i] <= nums[i - 1]) return false;
			}
			else return false;
		}
		return true;
	}
};

Solution

Approach 1: Brute Force

• 7ms, 26.62MB
• Complexity
  • Let $n$ be the length of the nums array, and $m$ denotes the maximum value in the nums array.
  • Time Complexity: $O(n \cdot m \cdot \sqrt{(m)})$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool checkPrime(int x) {
        for (int i = 2; i <= sqrt(x); i++) {
            if (x % i == 0) {
                return 0;
            }
        }
        return 1;
    }
    bool primeSubOperation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            int bound;
            // In case of first index, we need to find the largest prime less
            // than nums[0].
            if (i == 0) {
                bound = nums[0];
            } else {
                // Otherwise, we need to find the largest prime, that makes the
                // current element closest to the previous element.
                bound = nums[i] - nums[i - 1];
            }

            // If the bound is less than or equal to 0, then the array cannot be
            // made strictly increasing.
            if (bound <= 0) {
                return 0;
            }

            // Find the largest prime less than bound.
            int largestPrime = 0;
            for (int j = bound - 1; j >= 2; j--) {
                if (checkPrime(j)) {
                    largestPrime = j;
                    break;
                }
            }

            // Subtract this value from nums[i].
            nums[i] = nums[i] - largestPrime;
        }
        return 1;
    }
};

Approach 2: Storing the primes

• 6ms, 28.56MB
• Complexity
  • Let $n$ be the length of the nums array, and $m$ denotes the maximum value in the nums array.
  • Time Complexity: $O(n + m \cdot \sqrt{(m)})$
  • Space Complexity: $O(m)$

class Solution {
public:
    bool checkPrime(int x) {
        for (int i = 2; i <= sqrt(x); i++) {
            if (x % i == 0) {
                return 0;
            }
        }
        return 1;
    }
    bool primeSubOperation(vector<int>& nums) {
        int maxElement = *max_element(nums.begin(), nums.end());

        // Store the previousPrime array.
        vector<int> previousPrime(maxElement + 1, 0);
        for (int i = 2; i <= maxElement; i++) {
            if (checkPrime(i)) {
                previousPrime[i] = i;
            } else {
                previousPrime[i] = previousPrime[i - 1];
            }
        }

        for (int i = 0; i < nums.size(); i++) {
            int bound;
            // In case of first index, we need to find the largest prime less
            // than nums[0].
            if (i == 0) {
                bound = nums[0];
            } else {
                // Otherwise, we need to find the largest prime, that makes the
                // current element closest to the previous element.
                bound = nums[i] - nums[i - 1];
            }

            // If the bound is less than or equal to 0, then the array cannot be
            // made strictly increasing.
            if (bound <= 0) {
                return 0;
            }

            // Find the largest prime less than bound.
            int largestPrime = previousPrime[bound - 1];

            // Subtract this value from nums[i].
            nums[i] = nums[i] - largestPrime;
        }
        return 1;
    }
};

Approach 3: Sieve of Eratosthenes + Two Pointers

• 0ms, 28.63MB
• Complexity
  • Let $n$ be the length of the nums array, and $m$ denotes the maximum value in the nums array.
  • Time Complexity: $O(n + m \log \log(m))$
  • Space Complexity: $O(m)$

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        int maxElement = *max_element(nums.begin(), nums.end());

        // Store the sieve array.
        vector<int> sieve(maxElement + 1, 1);
        sieve[1] = 0;
        for (int i = 2; i <= sqrt(maxElement + 1); i++) {
            if (sieve[i] == 1) {
                for (int j = i * i; j <= maxElement; j += i) {
                    sieve[j] = 0;
                }
            }
        }

        // Start by storing the currValue as 1, and the initial index as 0.
        int currValue = 1;
        int i = 0;
        while (i < nums.size()) {
            // Store the difference needed to make nums[i] equal to currValue.
            int difference = nums[i] - currValue;

            // If difference is less than 0, then nums[i] is already less than
            // currValue. Return false in this case.
            if (difference < 0) {
                return 0;
            }

            // If the difference is prime or zero, then nums[i] can be made
            // equal to currValue.
            if (sieve[difference] == 1 or difference == 0) {
                i++;
                currValue++;
            } else {
                // Otherwise, try for the next currValue.
                currValue++;
            }
        }
        return 1;
    }
};