Leetcode 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.

• 특정 배열을 산이라고 부르기 위해선 아래와 같은 조건을 만족해야 한다.
  arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
• 위 조건을 만족하는 0 < i < arr.length - 1인 i가 존재해야 한다.
  • 즉, 왼쪽 슬로프와 오른쪽 슬로프가 있어야 한다는 의미
• 주어진 배열에서 최소한의 원소를 제거하여 산으로 만들때, 제거하는 최소한의 원소 수를 구하여라

에시

[2,1,1,5,6,2,3,1]

• index 0, 1, 5 를 제거하면
  [1,5,6,3,1]
• 가 된다.
• 답 3

제한

• $3 <= nums.length <= 1000$
• $1 <= nums[i] <= 10^9$
• 주어진 배열로 산을 반드시 만들수 있다.

풀이법

• LIS 알고리즘을 두번 쓰면 된다.
  • 산에서 줄어드는 부분이 왜 LIS냐? 줄어드는걸 거꾸로 보면 늘어나는거기 때문이다.
• LIS 알고리즘만 이해하면 사실상 끝

LIS 알고리즘 (Longest Increasing Subsequence)

LIS 알고리즘은 주어진 배열에서 가장 긴 증가 부분 수열(Longest Increasing Subsequence)의 길이를 구하는 방법 중 하나입니다. 이 방법은 이분 탐색을 활용하여, 각 요소가 오름차순으로 유지되도록 배열을 관리하면서 O(N log N)의 시간 복잡도로 해결할 수 있습니다.

이 알고리즘의 주요 개념은 dp라는 배열을 활용하여, 현재까지 탐색한 숫자들을 포함한 가장 짧은 길이의 증가 수열을 유지하는 것입니다. dp 배열을 스택처럼 사용하면서, 각 숫자를 오름차순으로 배치하여 가장 긴 증가 부분 수열의 길이를 도출할 수 있습니다.

알고리즘 단계별 설명

1. 배열 초기화

   • 배열의 길이를 N이라 하고, left라는 배열을 길이 N으로 초기화하여 각 인덱스에서의 LIS 길이를 저장합니다.
   • 빈 배열 dp를 생성하여 LIS의 가능한 증가 수열을 유지합니다.

2. 배열 순회 및 삽입 위치 탐색

   • 각 숫자 nums[i]에 대해, bisect_left 함수를 사용하여 dp 배열에서 nums[i]가 들어갈 위치를 이분 탐색으로 찾습니다.
   • 이 때 bisect_left(dp, nums[i])는 dp 배열에서 nums[i]보다 크거나 같은 첫 위치를 반환합니다. 이는 nums[i]가 들어갈 자리를 결정하는데 중요합니다.

3. dp 배열에 삽입

   • 찾은 위치가 dp의 마지막 위치라면, nums[i]가 dp 배열의 가장 큰 값이라는 뜻이므로, dp 배열의 끝에 nums[i]를 추가합니다.
   • 찾은 위치가 dp 배열의 중간이라면, dp 배열의 기존 값과 nums[i]를 교체하여 dp 배열의 길이를 유지하면서도 오름차순을 보장합니다. (이렇게 함으로써 dp 배열이 오름차순을 유지하고, 최적의 상태로 저장됩니다.)

4. LIS 길이 기록

   • left[i]에 dp의 현재 길이를 저장하여 nums[i] 위치까지의 LIS 길이를 기록합니다.

5. 결과 반환

   • 최종적으로 dp 배열의 길이는 주어진 배열의 가장 긴 증가 부분 수열의 길이입니다.

예제 코드

다음은 위 설명을 바탕으로 구현한 Python 코드입니다:

  from bisect import bisect_left

  def LIS(nums):
      N = len(nums)
      left = [0] * N  # 각 위치에서의 LIS 길이를 저장하는 배열
      dp = []  # LIS를 유지하는 배열

      for i in range(N):
          # 현재 숫자 nums[i]의 적절한 위치를 찾음
          l = bisect_left(dp, nums[i])

          # dp 배열의 끝에 넣을 수 있으면 추가, 중간에 삽입해야 하면 위치를 대체
          if len(dp) == l:
              dp.append(nums[i])
          else:
              dp[l] = nums[i]

          # 현재 인덱스까지의 LIS 길이를 저장
          left[i] = len(dp)

      return len(dp)  # LIS의 길이를 반환

이를 이용한 풀이법

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        N = len(nums)  # 배열 nums의 길이를 N에 저장

        left = [0] * N  # 각 인덱스에서 끝나는 왼쪽에서의 증가 부분 수열의 길이를 저장할 리스트
        right = [0] * N  # 각 인덱스에서 시작하는 오른쪽에서의 증가 부분 수열의 길이를 저장할 리스트

        dp = []  # 증가 부분 수열(LIS)을 저장할 임시 리스트
        for i in range(N):
            l = bisect.bisect_left(dp, nums[i])  # dp에서 nums[i]의 삽입 위치를 찾음
            if len(dp) == l:
                dp.append(nums[i])  # nums[i]가 dp의 가장 큰 값보다 크면 dp에 추가
            else:
                dp[l] = nums[i]  # 그렇지 않으면 dp의 위치 l에 nums[i]를 대체
            left[i] = len(dp)  # 현재까지의 증가 부분 수열의 길이를 left에 저장

        dp = []  # dp를 초기화하여 오른쪽에서의 LIS를 계산
        for i in range(N - 1, -1, -1):
            l = bisect.bisect_left(dp, nums[i])  # dp에서 nums[i]의 삽입 위치를 찾음
            if len(dp) == l:
                dp.append(nums[i])  # nums[i]가 dp의 가장 큰 값보다 크면 dp에 추가
            else:
                dp[l] = nums[i]  # 그렇지 않으면 dp의 위치 l에 nums[i]를 대체
            right[i] = len(dp)  # 현재까지의 증가 부분 수열의 길이를 right에 저장

        print(left, right)  # 디버깅을 위한 left와 right 출력

        ans = N  # 제거해야 하는 최소 원소 수를 N으로 초기화

        for i in range(N):
            if left[i] > 1 and right[i] > 1:  # 산의 봉우리를 형성할 수 있는 인덱스인지 확인
                ans = min(ans, N - left[i] - right[i] + 1)  # 최소 제거 원소 수 업데이트

        return ans  # 최소 제거해야 하는 원소 수 반환