[Leetcode][581] Shortest Unsorted Continuous Subarray

문제 : leetcode.com/problems/shortest-unsorted-continuous-subarray/

---

정수형 배열이 주어질 때, 연속적인 서브배열을 오름차순 정렬하면 전체 배열이 오름차순 정렬이 되게 하는 서브배열의 최소 길이를 구하라.

---

가장 간단한 방법은 주어진 배열을 오름차순 정렬한뒤 정렬한 배열과 기존 배열을 비교하면서 다른 요소값을 가지는 인덱스의 최소 값과 최대 값을 구한다. 최대값 - 최소값 + 1이 정답이된다.

이 방법으로 한 경우 정렬이 필요하므로 O(NlogN)의 시간이 소요된다.

 

문제에서는 선형복잡도로 풀 수 있는지 물었으므로 좀 더 효율적인 방법을 살펴보자.

[2,6,4,8,10,9,15] 를 예로 들어보자.

배열이 오름차순 정렬이라고 가정한다면,

왼쪽에서 오른쪽으로 탐색 시 탐색 중인 요소값은 이때까지 탐색한 값보다 같거나 커야한다.

오른쪽에서 왼쪽으로 탐색 시 탐색 중인 요소값은 이때까지 탐색한 값보다 작거나 같아야한다.

 

따라서 왼쪽에서 오른쪽으로 탐색하면서 요소의 최대값을 갱신시키면서 현재 탐색중인 값이 탐색한 값들중 최대값인지 판단한다. 만일 최대값이 아니라면 위 가정이 성립되지 못하므로 재정렬되어야한다. 따라서 현재 인덱스 값을 rightInd로 갱신한다.

이와 동일하게 이번에는 오른쪽에서 왼쪽으로 탐색한다. 최소값을 갱신시키면서 만일 탐색 중인 요소가 최소값이 아니라면 현재 인덱스 값을 leftInd로 갱신한다.

입력배열[leftInd, rightInd]가 재정렬 필요한 하위배열이 되므로 rightInd-leftInd+1이 정답이 된다.

예외적으로 만일 전체 배열이 정렬되어 있다면 0이 정답이 된다.

시간복잡도는 O(2N). 배열을 한 번 탐색하면서 배열[i], 배열[N-1-i]로 동시에 판단가능하므로 O(N)으로도 가능하다.

---

소스코드 

O(NlogN) : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/581.%20Shortest%20Unsorted%20Continuous%20Subarray(NlogN).cpp

O(N) : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/581.%20Shortest%20Unsorted%20Continuous%20Subarray(N).cpp