[코테연습] 1671. Minimum Number of Removals to Make Mountain Array

- DP / 배열 / 탐욕법 문제

 

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

 

- 문제분석

 

 

• 목표: 주어진 배열에서 최소한의 원소를 제거하여 배열을 산 모양 배열로 만드는 것.
  • 산 모양 배열이란 처음에는 오름차순으로 증가하고, 특정 정점을 기준으로 내림차순으로 감소하는 배열을 의미합니다.
  • 산 모양 배열의 길이는 3 이상이어야 하며, 정점(최대값) 이전에는 반드시 증가하는 부분이 있고, 이후에는 반드시 감소하는 부분이 있어야 합니다.
• 입력: 배열 nums가 주어지며, 배열의 길이는 n입니다.
• 조건:
  • 배열의 길이가 최소 3 이상이어야 산 모양 배열을 형성할 수 있습니다.
  • 산 모양 배열은 반드시 증가 부분과 감소 부분이 모두 존재해야 하므로, 정점은 배열의 첫 번째와 마지막 위치가 될 수 없습니다.
• 결과: 최소한의 원소를 제거하여 배열을 산 모양으로 만들기 위해 제거해야 하는 최소 원소 개수를 구하는 것입니다.

 

- 문제풀이

1. LIS (Longest Increasing Subsequence) 계산

• 목적: 배열의 각 인덱스에서 해당 위치까지의 가장 긴 증가 부분 수열의 길이를 계산합니다.
• 방법:
  • 배열을 왼쪽에서 오른쪽으로 순회하며, 현재 위치보다 작은 값을 가진 이전 인덱스들을 확인하여 현재 위치의 LIS 값을 갱신합니다.
  • 이중 반복문을 사용해 O(n^2) 시간 복잡도로 LIS를 계산합니다.

int[] LIS = new int[n];
Arrays.fill(LIS, 1);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            LIS[i] = Math.max(LIS[i], LIS[j] + 1);
        }
    }
}

 

 

 

• 모든 요소는 최소 길이 1로 초기화 (Arrays.fill(LIS, 1)).
• 각 요소 i에서 이전 요소들 j (j < i)와 비교해 nums[i] > nums[j]인 경우, 현재 위치의 LIS 길이를 갱신 (LIS[i] = max(LIS[i], LIS[j] + 1)).

 

2. LDS (Longest Decreasing Subsequence) 계산

• 목적: 배열의 각 인덱스에서 해당 위치부터 오른쪽으로의 가장 긴 감소 부분 수열의 길이를 계산합니다.
• 방법:
  • 배열을 오른쪽에서 왼쪽으로 순회하며, 현재 위치보다 큰 값을 가진 이후 인덱스들을 확인하여 현재 위치의 LDS 값을 갱신합니다.
  • 마찬가지로 O(n^2) 시간 복잡도로 계산합니다.

int[] LDS = new int[n];
Arrays.fill(LDS, 1);
for (int i = n - 1; i >= 0; i--) {
    for (int j = n - 1; j > i; j--) {
        if (nums[i] > nums[j]) {
            LDS[i] = Math.max(LDS[i], LDS[j] + 1);
        }
    }
}

 

 

 

• 모든 요소는 최소 길이 1로 초기화 (Arrays.fill(LDS, 1)).
• 각 요소 i에서 이후 요소들 j (j > i)와 비교해 nums[i] > nums[j]인 경우, 현재 위치의 LDS 길이를 갱신 (LDS[i] = max(LDS[i], LDS[j] + 1)).

 

3. 최대 산 모양 배열의 길이 (max_mountain_length) 계산

• 목적: 배열의 각 인덱스를 산 모양 배열의 정점으로 고려했을 때, 가능한 가장 긴 산 모양 배열의 길이를 계산합니다.
• 조건:
  • 산 모양 배열의 정점이 되기 위해서는 해당 인덱스에서 왼쪽으로 증가하고(LIS[i] > 1), 오른쪽으로 **감소(LDS[i] > 1)**해야 합니다.
  • 즉, 인덱스 i에서의 LIS와 LDS 모두 길이가 2 이상이어야 합니다.

int max = 0;
for (int i = 1; i < n - 1; i++) {
    if (LIS[i] > 1 && LDS[i] > 1) {
        max = Math.max(max, LIS[i] + LDS[i] - 1);
    }
}

 

 

 

• 인덱스 1부터 n-2까지 탐색합니다. 첫 번째와 마지막 인덱스는 산 모양 배열의 정점이 될 수 없습니다.
• LIS[i] + LDS[i] - 1을 계산하는 이유는 정점 i가 중복 계산되지 않도록 하기 위함입니다.
• max를 갱신하며 가장 긴 산 모양 배열의 길이를 추적합니다.

 

4. 제거해야 하는 최소 원소 개수 계산

• 목적: 가장 긴 산 모양 배열을 만들기 위해 제거해야 하는 원소의 개수를 계산합니다.
• 방법:
  • 전체 배열 길이에서 가장 긴 산 모양 배열의 길이를 빼면 제거해야 하는 최소 원소의 개수가 됩니다.

return n - max;

 

 

요약

• LIS 계산: 각 인덱스에서 왼쪽으로 증가하는 부분 수열의 길이를 계산합니다.
• LDS 계산: 각 인덱스에서 오른쪽으로 감소하는 부분 수열의 길이를 계산합니다.
• 최대 산 모양 배열의 길이 계산: 각 인덱스를 산 모양 배열의 정점으로 고려해 가장 긴 산 모양 배열을 찾습니다.
• 최소 제거 원소 개수 계산: 전체 길이에서 가장 긴 산 모양 배열의 길이를 빼서 최소 제거 원소 개수를 계산합니다.

 

 

> java

 

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] LIS = new int[n];
        int[] LDS = new int[n];
        Arrays.fill(LIS, 1);
        Arrays.fill(LDS, 1);
        
        // LIS 계산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
                }
            }
        }

        // LDS 계산
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    LDS[i] = Math.max(LDS[i], LDS[j] + 1);
                }
            }
        }

        // 최대 산 모양 배열 길이 계산
        int max = 0;
        for (int i = 1; i < n - 1; i++) {
            if (LIS[i] > 1 && LDS[i] > 1) {
                max = Math.max(max, LIS[i] + LDS[i] - 1);
            }
        }
        // 제거해야 하는 최소 원소의 개수를 반환
        return n - max;
    }
 
}

 

> python

 

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

        LIS = [1] * n
        LDS = [1] * n

        for i in range(n) :
            for j in range(i) :
                if nums[i] > nums[j] :
                    LIS[i] = max(LIS[i], LIS[j]+1)
        
        for i in range(n-1, -1, -1) :
            for j in range(i+1, n) :
                if nums[i] > nums[j] :
                    LDS[i] = max(LDS[i], LDS[j]+1)

        max_value = 0
        for i in range(1, n-1) :
            if LIS[i] > 1 and LDS[i] > 1 :
                max_value = max(max_value, LIS[i]+LDS[i]-1)
        
        return n - max_value