581. Shortest Unsorted Continuous Subarray

💡 풀이

// // O(NlogN)
var findUnsortedSubarray = function (nums) {
  let sorted = [...nums].sort((a, b) => a - b);

  let start = 0;
  let end = 0;

  for (let i = 0; i < sorted.length; i++) {
    if (sorted[i] !== nums[i]) {
      start = i;
      break;
    }
  }

  for (let j = sorted.length - 1; j >= 0; j--) {
    if (sorted[j] !== nums[j]) {
      end = j;
      break;
    }
  }

  if (!start && !end) return 0;
  return end - start + 1;
};

// O(N)
const findUnsortedSubarray = nums => {
  let min = 100000;
  let max = -100000;

  for (let i = 1; i < nums.length; i++) {
    let prev = nums[i - 1];
    let cur = nums[i];

    if (cur < prev) min = Math.min(min, cur);
  }

  for (let j = nums.length - 1; j >= 0; j--) {
    let prev = nums[j + 1];
    let cur = nums[j];

    if (cur > prev) max = Math.max(max, cur);
  }

  if (max === 0 && min === 100000) return 0;

  let start = 0;
  let end = 0;

  for (let k = 0; k < nums.length; k++) {
    if (min < nums[k]) {
      start = k;
      break;
    }
  }

  for (let u = nums.length - 1; u >= 0; u--) {
    if (max > nums[u]) {
      end = u;
      break;
    }
  }

  if (!start && !end) return 0;

  let answer = end - start + 1;

  return answer;
};



// 꺾이는 지점 중에서 가장 작은 값을 찾고 (앞에서부터 loop을 돌 때)
// 꺾이는 지점 중에서 가장 큰 값을 찾는다(뒤에서 부터 loop을 돌 때)

// 이후 해당 꺾이는 지점을 오른쪽으로 당겨준다. (앞에서부터 loop을 돌 때)
// 이후 해당 꺾이는 지점을 왼쪽으로 당겨준다. (뒤에서부터 loop을 돌 때)

📝 정리

1. 먼저 처음 내가 푼 방법이다. 시간 복잡도 O(NlogN)으로 풀었던 방법이다.

위의 그림을 참고해서 nums 배열과 sorted 배열을 비교하자.

• 원본 배열 nums와

• nums를 정렬한 배열 sorted라는 배열을 준비한다.

• 이후 앞에서부터 하나씩 비교하고 (순서대로 순회하는 반복문 사용) 처음 nums[i]와 sorted[i]가 다른 인덱스를 찾는다. (해당 인덱스 = start)

• 또한 뒤에서부터 하나씩 비교를 해서 (역순으로 순회하는 반복문 사용) nums[j]와 sorted[j]가 다른 인덱스를 찾는다. (해당 인덱스 = end)

• 이후 end - start + 1을 하면 그게 최소 정렬을 할 수 있는 subArray의 길이다.

2. 두 번째는 시간 복잡도 O(N)의 방법이다. 반복문 4개로 4 * N이기 때문에 결과적으로는 O(N)이다.

위의 그래프를 보자. 그래프를 nums 배열을 그래프로 표현한 그림이라고 생각해보자.

• 만약 0부터 순서대로 nums 배열을 순회한다고 생각했을 때, 꺾이는 지점(그래프가 아래로 내려가는 지점)이 바로 정렬을 해야되는 지점이다. 그 꺾이는 지점 중 가장 작은 값을 가지는 인덱스를 찾는다.

• 이번엔 끝에서부터 0까지 역순으로 nums 배열을 순회한다고 생각해보자. 꺾이는 지점(그래프가 위로 올라가는 지점)이 바로 정렬이 마무리 되어야 하는 지점이다. 그 꺾이는 지점 중 가장 큰 값을 가지는 인덱스를 찾는다.

• 가장 작은 값(이하 min)을 가지는 인덱스를 왼쪽으로 쭉 옮긴다. 그래프를 만날 때까지. 그래프를 만나는 지점의 인덱스가 정렬을 시작해야 하는 인덱스가 될 것이다. 만약 만나지 않는다면 인덱스 0, 즉 가장 첫부분이 정렬을 시작해야 하는 인덱스가 될 것이다.

• 가장 큰 값(이하 max)을 가지는 인덱스를 오른쪽으로 쭉 옮긴다. 그래프를 만날 때까지. 마찬가지로 그래프를 만나는 지점의 인덱스가 정렬이 마무리되어야 할 지점이 될 것이다. 만약 만나지 않는다면 인덱스가 nums.length - 1, 즉 가장 끝부분이 정렬이 마무리 되어야 하는 지점이 된다.

• 마지막으로, 옮긴 두 인덱스의 차 + 1을 해주면 subArray의 최소 길이가 나오게 된다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

LeetCode GitHub

https://github.com/tTab1204/LeetCode