2020.08.18 findUnsortedSubarray 풀이

문제 : 정수 배열이 주어지면, 오름차순으로 배열되지 않은 연속적인 sub-array의 갯수를 찾는 문제. 

 

풀이)

연속적인 sub-array 를 묻는 문제는 start / end 나 mid/result 같은 변수를 두개를 두어, 중간 과정을 기록하면서 마지막에 결과 값을 도출해내는 식의 풀이가 많은 것 같다. 이 문제의 경우,  오름 차순으로 정렬된 타겟 배열을 만들고, 모든 배열의 원소를 하나씩 순회하면서 타겟 배열과 값이 다를 때, 그 인덱스의 시작점을 start에 기록하고, end는 그 인덱스 중 가장 큰 수를 기록하는 식이다. 이런식으로 뭔가 중간의 값과 비교하면서 작거나 큰 값을 남겨야 할 때는 Math.min | Math.max 매소드를 활용하는 것이 좋다. 

 

이 때, Array.prototype.sort()는 원 배열을 바꾸는 mutable 한 속성이 있기 때문에, 원 배열을 복사한 후에 진행한다.

 

var findUnsortedSubarray = function(nums) {
  let sortedArr = [...nums].sort((a,b) => a - b);
  
  let start = nums.length - 1, end = 0;
  
  for(let i = 0; i < nums.length; i++) {
    if(sortedArr[i] !== nums[i]) {
      start = Math.min(start, i);
      end = Math.max(end, i);
    }
  }
  return start >= end ? 0 : end - start + 1;
}

 

103ms/ 걸려서 좀 더 나은 방법을 찾아보고 싶다.

 

 

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

Shortest Unsorted Continuous Subarray - LeetCode