1574. Shortest Subarray to be Removed to Make Array Sorted

1574. Shortest Subarray to be Removed to Make Array Sorted

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

---

오름차순을 만족하는 sequence 를 만드는 최소 크기의 SubArray 갯수를 계산합니다.

이는 크게 3 가지 경우를 생각합니다.

1. 앞쪽의 시퀀스 ( SubArray ) 를 제거하여 만족되는 경우

2. 뒷쪽의 시퀀스를 제거하여 만족되는 경우

3. 가운데 시퀀스를 제거하여 만족되는 경우

 

각 케이스 별로 나누지 않고 한 가지 구조로 검사할 수 있습니다.

주어진 sequence 에서 앞, 뒤로 오름차순이 만족되는 pivot 을 두고 이를 움직이는 방법 입니다.

 

예를 들어 앞쪽에서 오름차순이 만족되는 pivot ( begin ) 과 뒷쪽에서 오름차순이 만족되는 pivot ( end ) 를 두고 begin, end 사이에 존재하는 SubArray 에서 begin ( 앞쪽 시퀀스 ) 과 end ( 뒷쪽 시퀀스 ) 에 더 붙을 수 있는 ( swap ) 숫자를 검사하는 과정입니다.

 

위 과정은 begin 과 end 의 시퀀스 구성 요소에 대해 모두 수행합니다.

 

hint 로 해결하여 코드는 따로 첨부하지 않습니다.