Shortest Unsorted Continuous Subarray

• Reference
• 배열 문제를 해결할 때, 그래프를 고려해볼만한 문제다.
• 해당 배열에서 어떤 Sub 배열을 Sorting해야 전체 배열이 Sorting 되는지, 그 Sub 배열에 포함되는 원소는 몇개인지 구하는 문제였다.

Algorithm

2  7  5  6  3  9  15

• 처음으로 생각해볼만한 알고리즘으로는 sorting 후 배열과 비교하여 다른 부분을 찾는 것이다.

2  7  5  6  3  9  15

2  3  5  6  7  9  15
  p1       p2

• 비교하여 다른 부분을 찾아서 p1 ~ p2까지의 개수를 return 해주면 된다.

2  7  5  6  3  9  15

• 위와 같은 꺾은선 그래프 형태로 생각해볼 수 있다.

• 알고리즘은 간단하다.
• (-) -> (+) 변곡점 중 가장 작은 값을 왼쪽으로 자신의 자리에 맞는 곳으로 보내준다.
• (+) -> (-) 변곡점 중 가장 큰 값을 오른쪽으로 자신의 자리에 맞는 곳으로 보내준다.
• 이 자리에 맞는 곳으로 이동된 Index의 차이가 바꿔줘야하는 Subarray인 것이다.
• 이렇게할 수 있는 이유는 가장 작은 것이 왼쪽에서 가장 알맞은 위치로, 가장 큰 것이 오른쪽에서 가장 알맞은 위치로 이동 되므로 가운데 부분이 정렬되기만하면 우상향 되는 꺾은선 그래프 형태가 되는데 이는 Array가 정렬되었음을 의미할 수 있다.