2024 10 30 1671. Minimum Number of Removals to Make Mountain Array

문제

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.

요약

산 모양으로 왼쪽으로는 감소 오른쪽으로는 증가하는 최장 집합를 찾으면 된다.

풀이

dfs로 깊게 들어가면서 각 index (idx)에서 

1. 이전 0~idx 까지 가장 긴 증가 부분집합의 길이

2. 이후 idx ~ nums.length-1 까지 가장 긴 감소 부분집합의 길이

을 저장하고 두합이 가장 긴 부분집합을 찾고 이를 전체 길이에서 빼면된다.

 

이때 효율을 위해

1. 증가 부분집합을 찾을 시 현재까지 count보다 기존의 count가 클경우 return (왜냐면 이전값이 가장 큰것이기 때문에)

2. 감소 부분집합을 찾을 시 이미 값이 있을 경우 (이 경우는 이미 가장 깊은 값을 저장해주었으므로) 그 값을 반환

 

그리고 산모양이여야 함으로 증가 부분집합, 감소 부분집합 둘다 0보다 커야한다.

 

아래 코드에서는 감소부분집합에서 자기 자신을 포함시켰다

코드

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int[] downCount = new int[nums.length];
        int[] upCount = new int[nums.length];
        int max = 0;
        for (int idx = 0; idx < nums.length; idx ++){
            int up = upDfs(idx, 0, nums, upCount);
            int down = downDfs(idx, nums, downCount);
            if (downCount[idx] == 1 || upCount[idx] == 0) {
                continue;
            }
            max = Math.max(downCount[idx] + upCount[idx] , max);
        }
        return nums.length - max;
    }

    private int upDfs(int idx, int count, int[] nums, int[] upCount) {
        if (upCount[idx] >= count && upCount[idx] != 0) {
            return upCount[idx];
        }
        upCount[idx] = count;
        for (int i = idx; i < nums.length; i ++ ) {
            if (nums[i] > nums[idx]) {
                upDfs(i, count + 1, nums, upCount);
            }
        }
        return count;
    }

    private int downDfs(int idx, int[] nums, int[] downCount) {
        if (downCount[idx] != 0 ) {
            return downCount[idx];
        }
        int maxDown = 0;
        for (int i = idx; i < nums.length; i ++) {
            if (nums[i] >= nums[idx] && downCount[i] == 1) {
                break;
            }
            if (nums[i] < nums[idx]) {
               maxDown = Math.max(downDfs(i, nums, downCount) , maxDown);
            }
        }
        downCount[idx] = maxDown + 1;
        return downCount[idx];
    }
}

풀이 시간

20분

체감 난이도

중간쯤? 중간에 좀 해맴