[LeetCode] 2601 Prime Subtraction Operation

문제 링크 : https://leetcode.com/problems/prime-subtraction-operation/description/

🍊해결방법

• 배열이 주워졌을 때 i번째 수보다 작은 소수 중에서 적당한 수를 조작해서 증가하는 수열로 만들 수 있는지 판단
• N의 범위가 1000이므로 소수를 list에 담았다
• 결국 마지막 번째는 조작할 필요없으므로 뒤에서 부터 보면서 증가하는 수열을 만들자
• i번째에서 i+1번째 수를 보면서 소수list를 돌면서 i+1수 보다 작다면 만족 다음 수로 넘어가자
• 증가하는 수열로 만들 수 있으면 true 없으면 false

😀풀이

import java.util.*;

class Solution {
    public boolean primeSubOperation(int[] nums) {


        boolean isTrue = true;

        int N = nums.length;

        int before = nums[0];

        for(int i=1; i<N; i++){
            if(nums[i] > before){
                before = nums[i];
            }
            else{
                isTrue = false;
                break;
            }
        }

        if(isTrue){
            return true;
        }
        // 주어진 배열이 증가하는 수열이 아닐 때
        else{
            boolean check = true;

            boolean[] prime = new boolean[1001];
            // 소수인지
            for(int i=2; i*i<=1000; i++){
                for(int j=i*2; j<=1000; j+=i){
                    prime[j] = true;
                }
            }

            List<Integer> list = new ArrayList<>();

            for(int i=2; i<=1000; i++){
                if(!prime[i]){
                    list.add(i);
                }
            }

            // 배열의 뒤 부터 보자
            for(int i=N-2; i>=0; i--){
                int next = nums[i+1];

                if(next > nums[i]) continue;

                for(int j=0; j<list.size(); j++){
                    
                    if(list.get(j) >= nums[i]) break;

                    if(next > nums[i] - list.get(j)){
                        nums[i] -= list.get(j);
                        break;
                    }
                }

                // 작게 만드는 소수가 없을 때
                if(next <= nums[i]){
                    check = false;
                    break;
                }

            }

            //System.out.println(Arrays.toString(nums));

            return check;
        }

        
    }
}