[LeetCode] 1671. Minimum Number of Removals to Make Mountain Array

https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/description/?envType=daily-question&envId=2024-10-30

leetcode - Minimum Number of Removals to Make Mountain Array

문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍

문제 난이도: Hard

 

문제

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

 

만일 배열의 길이가 3 이상이고, 0 < i < arr.length -1의 i가 

• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

을 만족하면, mountain array라고 합니다.

mountain array를 만들기 위한 최소 요소 제거 횟수를 구하시오.

 

풀이

 

n을 전체 배열 길이라 하자.

산의 봉우리 peak를 두고, 그 peak를 기준으로 peak를 반드시 포함하는 0부터 peak까지의 LIS와 peak부터 n-1까지의 LDS의 길이를 전체 요소 길이 + 1에서 빼주면 된다.

(왼쪽제거: i+1 - len(LIS), 오른쪽제거: n-i - len(LDS), 전체 제거: 둘의 합이므로, n+1-len(LIS)-len(LDS))

 

모든 가능한 인덱스 1 ~ n-2의 요소들을 peak라 가정하고, 각각 그 기준의 LIS, LDS길이들을 구해둔다.

그리고, 가장 작은 n+1 - lis(peak) - lds(peak)를 구해서 반환하면 된다.

단, lis나 lds의 길이가 2 이상이어야 산의 형태이므로, 그 조건을 만족해야 한다.

 

코드

C++

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

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> lis(n, 1), lds(n, 1);

        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) lis[i] = max(lis[i], lis[j]+1);
            }
        }

        for(int i = n-2; i >= 0; --i) {
            for(int j = n-1; j > i; --j) {
                if(nums[i] > nums[j]) lds[i] = max(lds[i], lds[j]+1);
            }
        }

        int ans = INT_MAX;
        for(int i = 1; i < n-1; ++i) {
            if(lis[i] > 1 && lds[i] > 1) {
                ans = min(ans, n - lis[i] - lds[i] + 1);
            }
        }

        return ans;
    }
};