leetcode - Shortest Unsorted Continuous Subarray

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

Shortest Unsorted Continuous Subarray - LeetCode

 

<내가 짠 코드>

public int findUnsortedSubarray(int[] nums) {
		int[] originNums = new int[nums.length];
		int answer = nums.length;
		System.arraycopy(nums, 0, originNums, 0, nums.length);
		
		Arrays.sort(nums);
		
		// 원본이 오름차순 정렬되있는 경우는 0
		if (Arrays.equals(nums, originNums)) {
			answer = 0;
			return answer;
		}
		for (int i=0; i<originNums.length-1; i++) {
			int[] checkNums = new int[originNums.length];
			System.arraycopy(originNums, 0, checkNums, 0, nums.length);
			
			// subarray를 완전 탐색 방식으로 정렬된 nums과 비교해본다.
			for (int j=i+1; j<originNums.length; j++) {
				Arrays.sort(checkNums, i, j+1);
				if (Arrays.equals(checkNums, nums)) {
					int subArrNum = j-i+1;
					
					// 최소 subarray 길이를 저장
					if (answer > subArrNum) {
						answer = subArrNum;
					}
				}
			}
		}
		return answer;
}

원본 배열을 오름차순 정렬시키고, 그 배열과 완전 탐색으로 비교해보는 접근은 괜찮았던것 같다.

 

그러나 Time limit Exceeded로 통과되지 않음

 

 

 

<모범 답안>

public int findUnsortedSubarray(int[] nums) {
       int[] snums = nums.clone();
       Arrays.sort(snums);
       int start = snums.length, end = 0;
       for (int i = 0; i < snums.length; i++) {
           if (snums[i] != nums[i]) {
               start = Math.min(start, i);
               end = Math.max(end, i);
           }
       }
       return (end - start >= 0 ? end - start + 1 : 0);
}

for문을 하나만으로 풀 수 있다고한다... ㄷㄷㄷ

정렬된 배열과 비교할 배열을 요소별로 비교하면서

start 변수에는 subarray의 시작 인덱스, end 변수에는 끝 인덱스를 저장하고 계산하면 정답!!