문제 링크

내 코드

아이디어가 없음..

• 해설 읽기..

Solution

Overview

3가지 부분으로 나눠서 생각 가능.

1. 오름차순 정렬된 파란색 부분
2. 오름차순 정렬음 막는 노란 부분
3. 다시 오름차순으로 정렬된 초록 부분

2개의 예외 케이스

1. 이미 다 정렬된 경우 $\rightarrow$ 지울 subarray가 없음.
2. 반대로 정렬된 경우. $\rightarrow$ 제일 첫 원소만 남기거나 가장 마지막 원소만 남기거나.

제거 할 수 있는 가장 긴 부분 찾기.

Approach: Two Pointers

예시: [1, 2, 3, 10, 4, 2, 3, 5]

0을 정렬이 되지 않은 부분, 1을 정렬된 부분이라고 생각해보면, 다음과 같음. [0, 0, 0, 0, 0, 1, 1, 1]

정렬된 [1, 1, 1]에서 binary search를 통해 왼쪽 구역의 정렬된 마지막 원소를 어디에 넣을지 찾을 수 있음. $\rightarrow$ $O(n \log n)$

이 경우 two-pointer 사용 시 $O(n)$도 가능.

two pointer를 사용해보자( left and right).

• 접두사 파란색 배열: arr[0 : left]
• 접미사 녹색 배열: arr[right:]

이 two pointer 방법을 사용해여 왼쪽의 각 위치에 대해 arr[left] $\leq$ arr[right]인 가장 작은 오른쪽을 찾자. $\rightarrow$ 지워야 할 subarray 길이: right - left - 1

만약 arr[left] $>$ arr[right]이면 right를 증가시켜 다음 가능한 매칭을 찾고, 조건을 만족하는 right를 찾은 경우에, left를 다음 위치로 이동하자.

• 0ms, 69.5MB
• Complexity
  • Let N be the size of arr.
  • Time Complexity: $O(N)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int right = arr.size() - 1;
        while (right > 0 && arr[right] >= arr[right - 1]) {
            right--;
        }

        int ans = right;
        int left = 0;
        while (left < right && (left == 0 || arr[left - 1] <= arr[left])) {
            // find next valid number after arr[left]
            while (right < arr.size() && arr[left] > arr[right]) {
                right++;
            }
            // save length of removed subarray
            ans = min(ans, right - left - 1);
            left++;
        }
        return ans;
    }
};