[leetcode] 581. Shortest Unsorted Continuous Subarray

배열이 주어졌을때 어느영역만큼을 정렬하면 전체가 정렬된 상태일지 출력하는 문제이다.

가장 간단한 방식으로 접근해보면,

기존의 배열과 정렬된 배열을 양끝의 인덱스부터 비교하면서 서로 틀어지는 부분의 영역을 출력해주면 정답이 된다.

시간복잡도는 정력작업으로 인해 O(nlogn)이라서 수행속도를 보면 별로 빠르지 않다.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        vector<int> numsCpy = nums;
        sort(numsCpy.begin(), numsCpy.end());
        
        int left = 0;
        int right = nums.size() - 1;
        
        while(left < right){
            bool checked = false;
            if(nums[left] == numsCpy[left]) {
                left++;
                checked = true;
            }
            if(nums[right] == numsCpy[right]) {
                right--;
                checked = true;
            }
            
            if(!checked) break;
        }
        
        return left == right ? 0 : right - left + 1;
    }
};

 

 

암만봐도 정렬없이 O(n) 복잡도로 풀어야할 것 같다.

 

O(n)으로 풀었습니다!! 🚀🚀🚀 

실행결과 확인해보면 거이 최적에 가까운 해로 보이네요

컨셉은 간단합니다.

각각의 인덱스를 순회하면서 순서가 뒤집혀있는 곳을 찾고 그떄의 정보를 잘 저장해두어서 답을 구합니다.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        
        int left = -1;
        int right = -1;
        int start = -1;

        int before = nums[0];
        for(int i = 1; i<nums.size(); i++){
        	// 정렬되어 있다면 continue
            if(before <= nums[i]) {
                before = nums[i];
                continue;
            }
			
            // 부분적으로 순서가 뒤집힌 곳의 앞뒤를 left, right로
            left = i - 1;
            right = i;
            bool checked = false;
			
            // left 이전에 right보다 작은녀석이 있다면 left를 왼쪽으로
            while(left >= 0 && nums[left] > nums[right]){
                left--;
                checked = true;
            }
            if(checked) left++;

			// left를 저장해둬서 처리
            if(start == -1 || start > left) start = left;
            int tmp = nums[i];
            nums[i] = before;
            nums[i - 1] = tmp;

            
        }
        
        return start == right ? 0 : right - start + 1;
    }
};