[LeetCode] 2369. Check if There is a Valid Partition For The Array

https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array/description/

Check if There is a Valid Partition For The Array - LeetCode

문제 유형 : 동적 계획법(다이나믹 프로그래밍)

문제 난이도 : Medium

 

문제

You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:

1. The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
2. The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
3. The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.

Return true if the array has at least one valid partition. Otherwise, return false.

 

배열을 아래의 규칙대로 쪼갤 수 있으면 true를, 아니면 false를 반환하시오.

1. 정확히 두 요소가 일치할 경우
2. 정확히 세 요소가 일치할 경우
3. 세 연속된 수가 1씩 증가하는 경우

 

풀이

dp테이블을 만들어서 dp[i]가 nums[i-1]까지의 가능 여부를 저장한다.

 

dp[0]에는 true를 넣어준다.

 

우선, 2개의 동일한 연속된 숫자를 발견하고, 그 이전까지 유효하게 분할되었으면(2칸 이전의 dp값이 true면) true를 저장한다. 

 

그리고 3개의 동일한 숫자 또는 연속되는 패턴을 발견하고, 그 이전까지 유효하게 분할되었으면(3칸 이전의 dp값이 true면) true를 저장한다.

 

마지막 dp[n]에는 nums[n-1]까지의 배열, 즉 nums배열 전체의 유효한 분할 여부가 담겨있으므로, 이를 반환해주면 된다.

 

코드

C++

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        const int n = nums.size();

        vector<bool> dp(n + 1, false);
        dp[0] = true;
    
        for (int i = 1; i <= n; i++) {
            if (i >= 2 && nums[i - 1] == nums[i - 2] && dp[i - 2]) {
                dp[i] = true;
            }
            if (i >= 3) {
                if ((nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) || 
                    (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1)) {
                    if (dp[i - 3]) {
                        dp[i] = true;
                    }
                }
            }
        }

        return dp[n];
    }
};

 

Python3

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * (n+1)
        dp[0] = True
    
        for i in range(1, n+1):
            if i >= 2 and nums[i-1] == nums[i-2] and dp[i-2]:
                dp[i] = True
            if i >= 3:
                if (nums[i-1] == nums[i-2] == nums[i-3] or
                    (nums[i-1] == nums[i-2] + 1 and nums[i-2] == nums[i-3] + 1)) and dp[i-3]:
                    dp[i] = True
    
        return dp[n]

 

Dart

class Solution {
  bool validPartition(List<int> nums) {
    int n = nums.length;
    List<bool> dp = List<bool>.filled(n+1, false);
    dp[0] = true;

    for(int i = 1; i <= n; i++) {
      if(i >= 2 && nums[i-1] == nums[i-2] && dp[i-2]) {
        dp[i] = true;
      }
      if(i >= 3){
        if((nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) || (nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1)) {
          if(dp[i-3]){
            dp[i] = true;
          }
        }
      }
    }
    return dp[n];
  }
}

 

Java

class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;

        boolean[] dp = new boolean[n+1];
        dp[0] = true;

        for(int i = 1; i <= n; i++) {
            if(i >= 2 && nums[i-1] == nums[i-2] && dp[i-2]) {
                dp[i] = true;
            }
            if(i >= 3) {
                if((nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) ||
                nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1) {
                    if(dp[i-3]) {
                        dp[i] = true;
                    }
                }
            }
        }

        return dp[n];
    }
}

 

Swift

class Solution {
    func validPartition(_ nums: [Int]) -> Bool {
        var n = nums.count
        var dp = Array(repeating: false, count: n+1)
        dp[0] = true

        for i in 1...n {
            if i >= 2 && nums[i-1] == nums[i-2] && dp[i-2] {
                dp[i] = true
            }
            if i >= 3 {
                if (nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) || (nums[i-1] == nums[i-2] + 1 && nums[i-2] == nums[i-3] + 1){
                    if(dp[i-3]){
                        dp[i] = true
                    }
                }
            }
        }

        return dp[n]
    }
}