1671. Minimum Number of Removals to Make Mountain Array

[zeikar]

Problem link

https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/

Problem Summary

배열에서 최소한의 원소를 제거하여 mountain-array 가 하도록 하는 문제.
mountain-array는 순서대로 원소가 커졌다가 작아지는 배열이다.

Solution

처음엔 LIS 안 쓰고 무식하게 DP를 돌렸는데 Wrong Answer 몇개 후 MLE 까지 떴다... 아래 discuss 느낌으로 구현했는데 top-down이라 메모리를 많이 먹은 듯..
https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/discuss/952003/Java-DP-O(n2)-Got-TLE-NEED-HELP!

결국 LIS를 쓰기로 결정.
먼저 최소한의 원소를 제거해서 mountain-array를 만든다는 것은 반대로 말하면 배열 안에서 최대 길이의 mountain-array를 찾으면 그게 정답이다.

최대 길이의 mountain-array는 LIS를 두 번 돌려서 간단하게 구할 수 있다.

먼저 증가하는 LIS를 한번 돌리고 배열의 뒤에서부터 LIS를 한번 더 돌려주면 된다.(LDS) 그렇게 되면 현재 인덱스까지의 최대 증가 수열과 현재 인덱스 부터의 최대 감소 수열의 개수을 구할 수 있고 이를 더한 후 -1 뺀 값이 바로 최대 길이의 mountain-array가 된다.
증가 수열, 감소 수열에서 중복으로 세줬으므로 1을 빼줘야 한다.

하나 주의할 점은 최대 길이를 구할 때 LIS, LDS 둘 다 1 초과인 값으로 갱신해줘야 한다. 1인 경우 peak를 찍고 내려오는 것이 포함이 안되어 있다.

추가로 **이분 탐색으로 LIS 를 O(n log n)**으로 줄일 수 있지만 인풋 크기가 작으므로 O(n^2)으로도 충분히 돌아간다.

Source Code

from typing import List


class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:

        lis_dp = [1] * len(nums)
        lds_dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    lis_dp[i] = max(lis_dp[i], lis_dp[j] + 1)

        for i in range(len(nums) - 2, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[i] > nums[j]:
                    lds_dp[i] = max(lds_dp[i], lds_dp[j] + 1)

        ans = 1987654321
        for i in range(1, len(nums) - 1):
            ans = min(ans, len(nums) - (lis_dp[i] + lds_dp[i] - 1))

        return ans