[LeetCode] 581 Shortest Unsorted Continuous Subarray JavaScript

문제 링크

Shortest Unsorted Continuous Subarray - LeetCode

 

문제 유형

투 포인터, 정렬

 

문제 풀이

이 문제는 배열 내 모든 원소가 오름차순 정렬이 되도록 정렬되지 않은 subarray를 정렬할 때의 최소 subarray의 길이를 구하는 문제이다. 해당 문제는 두가지 방법으로 접근 가능하다.

• 정렬 후 비교하기
  1. 입력으로 주어진 배열을 정렬해 새로운 배열에 복사한다.
  2. 브루트 포스 방법으로 원래 배열의 요소와 새로운 배열의 요소를 비교하여 요소가 일치하지 않는 시작점과 끝점을 파악한다.
  위와 같은 방법은 O(nlogn)의 시간 복잡도를 갖는다.
• 투 포인터
  오름차순 정렬된 배열의 첫 요소부터 접근하면 최댓값은 계속 변한다. 반대로, 마지막 요소부터 접근하면 최소값은 계속 변한다. 따라서, 배열을 처음부터 탐색해 현재 요소가 최댓값보다 작으면 정렬되지 않은 것이므로 subarray의 끝점을 갱신해준다. 반대로, 배열을 끝에서부터 탐색해 현재 요소가 최소값보다 크면 정렬되지 않은 것이므로 subarray의 시작점을 갱신해준다.
  위와 같은 방법은 O(n)의 시간 복잡도를 갖는다.

배열의 첫 요소부터 탐색하는 과정

배열의 마지막 요소부터 탐색하는 과정

 

코드

// Two Pointer
var findUnsortedSubarray = function(nums) {
    const n = nums.length - 1;
    let start = -1, end = -2; // nums가 정렬되어 있을 때는 0을 출력하기 위한 변수 초기 설정
    let max = nums[0], min = nums[n];
    
    for (let i = 1; i <= n; i++) {
        nums[i] >= max ? max = nums[i] : end = i;
        nums[n - i] <= min ? min = nums[n - i] : start = n - i;
    }
    return end - start + 1;
};

 

참고

https://www.youtube.com/watch?v=BmLLbuumuww

https://www.youtube.com/watch?v=Z4DJwKEFkNI